LIS
首先LIS为最长子序列，我们有一个朴素的DP求LIS，时间规模为O（n2)
代码如下
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 1000005;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false);
int n;
int s[MAXN];
int dp[MAXN];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", s + i);
}
int res = 0;
for (int i = 1; i <= n; i++) {
dp[i] = 1;
for (int j = 1; j <= i; j++) {
if (s[i] > s[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
res = max(res, dp[i]);
}
printf("%d\n", res);
return 0;
}
如果要输出路径也很简单，只要在每次DP的时候加一个前驱元素就行，然后通过递归输出路径
但很明显如果N的数据规模变大了将无法在有限时间内解决问题，也就是一种暴力枚举。
此时就要用另一种方法,此时dp[i]代表上升子序列长度为i时最小末尾数值，然后开始遍历序列，如果此时该元素大于目前最大长度的最小末尾数则更新最大长度；
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 1000005;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false);
int a[MAXN];
int f[MAXN];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
f[i] = INF;//方便以后更新最长序列
}
f[1] = a[1];
int len = 1;
for (int i = 2; i <= n; i++) {
int l = 0, r = len;
if (a[i] > f[len]) {
f[++len] = a[i];//如果大于则更新最长序列
} else {
while (r - l > 1) {//用二分查找最后一个小于它的元素，更新它下一个元素的最小末尾数，因为数组内保存的是最小末尾，所以一定是递增的
int mid = (l + r) >> 1;
if (f[mid] > a[i]) {
r = mid;
} else {
l = mid;
}
}
f[r] = min(a[i], f[r]);
}
}
printf("%d", len);
return 0;
}
LCS
?先来看一下最朴素的算法，时间复杂度也是O（n2）规模一大就会被卡
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 1000005;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false);
int dp[105][105];
int a[105];
int b[105];
int n,m;
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",a+i);
}
for(int i=1;i<=m;i++){
scanf("%d",b+i);
}
for(int i=1;i<=n;i++){
for(int j=1;j<m;j++){
if(a[i]==b[j]){
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
}else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
printf("%d",dp[n][m]);
return 0;
}
所以可以来考虑一下O（nlogn）的算法
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 1000005;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false);
const int N = 1e5 + 5;
int a[N], b[N], mp[N], f[N];
int main() {
int n;
memset(f, INF, sizeof(f));
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
mp[a[i]] = i;//建立一个B在A中位置的表
}
for (int i = 1; i <= n; i++) {
scanf("%d", b + i);
}
int len = 0;
f[0] = 0;
for (int i = 1; i <= n; i++) {
int l = 0, r = len, mid;
if (mp[b[i]] > f[len]) {//转换为LIS问题，即将B中元素转换为A中元素且带有序号；
f[++len] = mp[b[i]];
} else {
while (r - l > 1) {
mid = (r + l) >> 1;
if (f[mid] > mp[b[i]]) {
r = mid;
} else {
l = mid;
}
}
f[l + 1] = min(mp[b[i]], f[l + 1]);
}
}
printf("%d", len);
return 0;
}
?
|