Greatest Common Increasing Subsequence
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1432
题目大意：给出两串数字，求他们的最长公共上升子序列（LCIS），并且打印出来。
Sample Input
1
5
1 4 2 5 -12
4
-12 1 2 4
Sample Output
2
1 4
分析：神奇就神奇在是LIS与LCS的组合
令dp[i][j]表示A串的前i个，与B串的前j个，并以B[j]为结尾的LCIS 的长度.
状态转移方程：
f(A[i]==B[j]) dp[i][j]=max(dp[i-1][k])+1; ( 1 <= k < j )
else dp[i][j]=dp[i-1][j];
然后选择循环顺序，就可以将算法的复杂度降为n*n.
代码如下：
/*这个代码结果虽然对，跟样例的输出都不一样，而且两个输出数据之间有空行都没有实现，却能AC，有点匪夷所思*/
# include<stdio.h>
# include<string.h>
#define MAX 550 struct node{
int x,y;
}path[MAX][MAX]; int dp[MAX][MAX];
int s[MAX],t[MAX]; int main(){
int T,i,j;
scanf("%d",&T);
while(T--)
{
memset(path,,sizeof(path));
int n,m;
scanf("%d",&n);
for(i=; i<=n; i++)
scanf("%d",&s[i]);
scanf("%d",&m);
for(i=; i<=m; i++)
scanf("%d",&t[i]);
memset(dp,,sizeof(dp));
int max = ;
for(i=; i<=n; i++)
{
max = ;
int tx = ,ty = ;
for(j=; j<=m; j++)
{
dp[i][j] = dp[i-][j];
path[i][j].x = i-;
path[i][j].y = j;
if( s[i] > t[j] && max < dp[i-][j])
{
max = dp[i-][j];
tx = i-;
ty = j;
}
if( s[i] == t[j] )
{
dp[i][j] = max+;
path[i][j].x = tx;
path[i][j].y = ty;
}
}
}
max = -;
int id;
for(i=; i<=m; i++)
if(dp[n][i]>max)
{
max = dp[n][i];
id = i;
}
int save[MAX];
int cnt=;
int tx,ty;
tx=n; ty=id;
while(dp[tx][ty] != )
{
int tmpx,tmpy;
tmpx = path[tx][ty].x;
tmpy = path[tx][ty].y;
if(dp[tx][ty] != dp[tmpx][tmpy])
{
save[cnt++]=t[ty];
}
tx = tmpx; ty = tmpy;
}
printf("%d\n",max);
for(i=cnt-; i>=; i--)
printf("%d ",save[i]);
printf("\n");
}
return ;
}