LIS 最长上升子序列
#include <iostream>
#include <algorithm>
using namespace std;
int a[1001],ans[1001],len;
int main()
{int n,T;cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];ans[1]=a[1];len=1;for(int i=2;i<=n;i++){if(a[i]>ans[len])ans[++len]=a[i];else{int pos=lower_bound(ans+1,ans+len+1,a[i])-ans;ans[pos]=a[i];}}cout<<len<<endl;}return 0;
}
LCS 最长公共子序列
状态转移方程：
if(s1[i]==s2[j]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}dp数组：
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| i | b | d | c | a | b | a | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 1 | a | 0 |
0 | 0 | 0 | 1 | 1 | 1 |
| 2 | b | 0 | 1 |
1 |
1 | 1 | 2 | 2 |
| 3 | c | 0 | 1 | 1 | 2 |
2 |
2 | 2 |
| 4 | b | 0 | 1 | 1 | 2 | 2 | 3 |
3 |
| 5 | d | 0 | 1 | 2 | 2 | 2 | 3 |
3 |
| 6 | a | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
| 7 | b | 0 | 1 | 2 | 2 | 3 | 4 | 4 |
加黑的数字为回溯过程
if(s1[i]==s2[j]){prn(i-1,j-1);cout<<s1[i];}else{if(dp[i-1][j]>dp[i][j-1])prn(i-1,j);elseprn(i,j-1);}#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
char s1[1001],s2[1001];
int dp[1001][1001]={0};
void prn(int i,int j)
{if(!i||!j)return ;else{if(s1[i]==s2[j]){prn(i-1,j-1);cout<<s1[i];}else{if(dp[i-1][j]>dp[i][j-1])prn(i-1,j);elseprn(i,j-1);}}return ;
}
int main()
{while(~scanf("%s%s",s1+1,s2+1)){memset(dp,0,sizeof(dp));int len1,len2;s1[0]='*';s2[0]='.';len1=strlen(s1);len2=strlen(s2);for(int i=1; i<len1; i++){for(int j=1; j<len2; j++){if(s1[i]==s2[j]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}}printf("%d\n",dp[len1-1][len2-1]); //最长公共子序列的长度prn(len1-1,len2-1); //输出其中一个的最长公共子序列}return 0;
}