题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1423 题意：如题… 题解： LCS与LIS的合体 显然用DP解，DP状态的定义比较巧妙 先把暴力写出来
然后考虑它的优化 对于第二个状态转移方程，每次需要枚举f【i-1】【k】，其中有很多冗余的更新 其中有效的更新只有当k=j时的一次 换而言之，每次只向决策集合之中添加一个新的决策 所以只需要定义一个临时变量记录枚举到一个 j 时 f【i-1】【k】的最大值即可 复杂度由O（n^3）降到O（n^2）
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int a[510],b[510],f[510][510],t,n,lena,lenb,ans; int main() { scanf("%d",&t); while(t--) { scanf("%d",&lena); for(int i=1;i<=lena;i++) scanf("%d",&a[i]); scanf("%d",&lenb); for(int i=1;i<=lenb;i++) scanf("%d",&b[i]); int temp=0; /*正常的O（n^3）写法 for(int i=1;i<=lena;i++) for(int j=1;j<=lenb;j++) { if(a[i]!=b[j]) f[i][j]=f[i-1][j]; else for(int k=1;k<=j;k++) if(b[k]<a[i])// a[i]=b[j] f[i][j]=max(f[i][j],f[i-1][k]+1); }*/ for(int i=1;i<=lena;i++) { temp=0;//用于记录当前最大值 for(int j=1;j<=lenb;j++) { if(a[i]!=b[j]) f[i][j]=f[i-1][j]; if(b[j]<a[i]) temp=max(temp,f[i-1][j]);//更新最大值 if(a[i]==b[j]) f[i][j]=temp+1; } } ans=0; for(int i=1;i<=lenb;i++) ans=max(f[lena][i],ans); printf("%d\n",ans); if(t) printf("\n"); } }POJ2127 +记录路径
