题目：http://poj.org/problem?id=2127
十分费劲地终于记录好了路径……用一个前驱。
这是 n^2 的LICS方法。其实就是 n ^ 2 log n 把“找之前的d [ j ]的max”用树状数组弄成了 n ^ 2，而这个则在每个 i 遍历 j 的时候顺便更新记录好了要用的那个值，就线性了。
j 是脚标。k 的更新有时间差，保证了“只能用脚标比自己小的”这个条件。
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; int n,m; bool use[505][505]; ll a[505],b[505],d[505],pre[2][505][505];//0是行，1是列；表示第i行与j匹配时 void print(ll cnt,ll k) //用了这个i吗？(和j匹配时)(use[i][j]) { //上一个是？(行是0，上一行与pre[1]匹配时，以定位) // printf("(cnt=%lld k=%lld)",cnt,k); if(!cnt)return; print(pre[0][cnt][k],pre[1][cnt][k]); if(use[cnt][k])printf("%lld ",b[k]);//主要用在cnt==n时判断输出此i否 } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); scanf("%d",&m); for(int i=1;i<=m;i++)scanf("%lld",&b[i]); for(int i=1;i<=n;i++) { ll k=0; for(int j=1;j<=m;j++) //若没有选此i，行是之前的(就像d的自然copy一样) { if(use[i-1][j]) { pre[0][i][j]=i-1;pre[1][i][j]=j; } else { pre[0][i][j]=pre[0][i-1][j];pre[1][i][j]=pre[1][i-1][j]; } } for(int j=1;j<=m;j++) { if(a[i]>b[j]&&d[j]>d[k])k=j; else if(a[i]==b[j]&&d[j]<d[k]+1)//选此i { d[j]=d[k]+1; if(use[i-1][k]) { pre[0][i][j]=i-1;pre[1][i][j]=k; } else { pre[0][i][j]=pre[0][i-1][k];pre[1][i][j]=k;//用的不是上一行的j，而是k } use[i][j]=1; } } } ll mx=0,k=0; for(int i=1;i<=m;i++) if(d[i]>mx)mx=d[i],k=i; printf("%lld ",mx); print(n,k); return 0; }
为什么这个比上一个慢？
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; int n,m; bool use[505][505]; ll a[505],b[505],d[505],pre[2][505][505];//0是行，1是列；表示第i行与j匹配时 void print(ll cnt,ll k) //用了这个i吗？(和j匹配时)(use[i][j]) { //上一个是？(行是0，上一行与pre[1]匹配时，以定位) // printf("(cnt=%lld k=%lld)",cnt,k); if(!cnt)return; print(pre[0][cnt][k],pre[1][cnt][k]); // if(use[cnt][k])printf("%lld ",b[k]);//主要用在cnt==n时判断输出此i否 printf("%lld ",b[k]); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); scanf("%d",&m); for(int i=1;i<=m;i++)scanf("%lld",&b[i]); for(int i=1;i<=n;i++) { ll k=0; for(int j=1;j<=m;j++) //若没有选此i，行是之前的(就像d的自然copy一样) { if(use[i-1][j]) { pre[0][i][j]=i-1;pre[1][i][j]=j; } else { pre[0][i][j]=pre[0][i-1][j];pre[1][i][j]=pre[1][i-1][j]; } } for(int j=1;j<=m;j++) { if(a[i]>b[j]&&d[j]>d[k])k=j; else if(a[i]==b[j]&&d[j]<d[k]+1)//选此i { d[j]=d[k]+1; if(use[i-1][k]) { pre[0][i][j]=i-1;pre[1][i][j]=k; } else { pre[0][i][j]=pre[0][i-1][k];pre[1][i][j]=k;//用的不是上一行的j，而是k } use[i][j]=1; } } } ll mx=0,k=0; for(int i=1;i<=m;i++) if(d[i]>mx)mx=d[i],k=i; printf("%lld ",mx); if(use[n][k])print(n,k); else print(pre[0][n][k],k); return 0; }
另一种记录路径的方法
#include<iostream> #include<cstdio> #define ll long long using namespace std; const ll INF=503;//////防RE，不能大于底下的数组 ll n,m; ll a[505],b[505],d[505],pre[505][505]; bool prin[505]; void print(ll i,ll j) { if(!i)return; print(i-1,pre[i][j]); if(pre[i-1][j]!=pre[i][j]&&!prin[j])printf("%lld ",b[j]),prin[j]=1;//以防真实匹配的i的后一个非真实时的输出 // printf("i=%d j=%d ",i,j); //用d的值判断比较方便，但不想开二维 } int main() { scanf("%lld",&n); for(ll i=1;i<=n;i++)scanf("%lld",&a[i]); scanf("%lld",&m); for(ll i=1;i<=m;i++)scanf("%lld",&b[i]); for(ll i=1;i<=n;i++) { ll k=0; for(ll j=1;j<=m;j++) { pre[i][j]=j; if(a[i]>b[j]&&d[j]>d[k])k=j; else if(a[i]==b[j]&&d[j]<d[k]+1) { d[j]=d[k]+1; pre[i][j]=k;//当i是第一个，且i与某个匹配时，i的pre与i-1(0)的pre相同了 if(!k)pre[i][j]=INF; } } } ll k=0,mx=0; for(ll i=1;i<=m;i++) if(d[i]>mx)mx=d[i],k=i; printf("%lld ",mx); print(n,k); }