题目链接：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 +记录路径