题意
。。最长公共子序列 简单易懂的题面
题解
。。基础dp 没啥说的。。不过看了一下还是有优化的思路 可以找到第一个序列在第二个序列中的出现位置，这样出现位置的序列来做最长上升子序列 利用二分在理论上可以到O(nlogn)的复杂度 不过 依旧是懒得实践（
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[1200][1200];
char x[1200],y[1200];
int main(){
while(~scanf("%s%s",x,y)){
memset(dp,0,sizeof(dp));
int i,j;
for(i=0;x[i]!='\0';++i){
for(j=0;y[j]!='\0';++j){
dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
if(x[i]==y[j]){
dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1);
}
}
}
printf("%d\n",dp[i][j]);
}
return 0;
}
|