题目：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[][];
ll a[],b[],d[],pre[][][];//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[][cnt][k],pre[][cnt][k]);
if(use[cnt][k])printf("%lld ",b[k]);//主要用在cnt==n时判断输出此i否
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%lld",&a[i]);
scanf("%d",&m);
for(int i=;i<=m;i++)scanf("%lld",&b[i]);
for(int i=;i<=n;i++)
{
ll k=;
for(int j=;j<=m;j++) //若没有选此i，行是之前的(就像d的自然copy一样)
{
if(use[i-][j])
{
pre[][i][j]=i-;pre[][i][j]=j;
}
else
{
pre[][i][j]=pre[][i-][j];pre[][i][j]=pre[][i-][j];
}
}
for(int j=;j<=m;j++)
{
if(a[i]>b[j]&&d[j]>d[k])k=j;
else if(a[i]==b[j]&&d[j]<d[k]+)//选此i
{
d[j]=d[k]+;
if(use[i-][k])
{
pre[][i][j]=i-;pre[][i][j]=k;
}
else
{
pre[][i][j]=pre[][i-][k];pre[][i][j]=k;//用的不是上一行的j，而是k
}
use[i][j]=;
}
}
}
ll mx=,k=;
for(int i=;i<=m;i++)
if(d[i]>mx)mx=d[i],k=i;
printf("%lld\n",mx);
print(n,k);
return ;
}
为什么这个比上一个慢？
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int n,m;
bool use[][];
ll a[],b[],d[],pre[][][];//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[][cnt][k],pre[][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=;i<=n;i++)scanf("%lld",&a[i]);
scanf("%d",&m);
for(int i=;i<=m;i++)scanf("%lld",&b[i]);
for(int i=;i<=n;i++)
{
ll k=;
for(int j=;j<=m;j++) //若没有选此i，行是之前的(就像d的自然copy一样)
{
if(use[i-][j])
{
pre[][i][j]=i-;pre[][i][j]=j;
}
else
{
pre[][i][j]=pre[][i-][j];pre[][i][j]=pre[][i-][j];
}
}
for(int j=;j<=m;j++)
{
if(a[i]>b[j]&&d[j]>d[k])k=j;
else if(a[i]==b[j]&&d[j]<d[k]+)//选此i
{
d[j]=d[k]+;
if(use[i-][k])
{
pre[][i][j]=i-;pre[][i][j]=k;
}
else
{
pre[][i][j]=pre[][i-][k];pre[][i][j]=k;//用的不是上一行的j，而是k
}
use[i][j]=;
}
}
}
ll mx=,k=;
for(int i=;i<=m;i++)
if(d[i]>mx)mx=d[i],k=i;
printf("%lld\n",mx);
if(use[n][k])print(n,k);
else print(pre[][n][k],k);
return ;
}
另一种记录路径的方法
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll INF=;//////防RE，不能大于底下的数组
ll n,m;
ll a[],b[],d[],pre[][];
bool prin[];
void print(ll i,ll j)
{
if(!i)return;
print(i-,pre[i][j]);
if(pre[i-][j]!=pre[i][j]&&!prin[j])printf("%lld ",b[j]),prin[j]=;//以防真实匹配的i的后一个非真实时的输出
// printf("i=%d j=%d\n",i,j); //用d的值判断比较方便，但不想开二维
}
int main()
{
scanf("%lld",&n);
for(ll i=;i<=n;i++)scanf("%lld",&a[i]);
scanf("%lld",&m);
for(ll i=;i<=m;i++)scanf("%lld",&b[i]);
for(ll i=;i<=n;i++)
{
ll k=;
for(ll j=;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]+)
{
d[j]=d[k]+;
pre[i][j]=k;//当i是第一个，且i与某个匹配时，i的pre与i-1(0)的pre相同了
if(!k)pre[i][j]=INF;
}
}
}
ll k=,mx=;
for(ll i=;i<=m;i++)
if(d[i]>mx)mx=d[i],k=i;
printf("%lld\n",mx);
print(n,k);
}