POJ - 2127 Greatest Common Increasing Subsequence
You are given two sequences of integer numbers. Write a program to determine their common increasing subsequence of maximal possible length.
Sequence S 1 , S 2 , . . . , S N of length N is called an increasing subsequence of a sequence A 1 , A 2 , . . . , A M of length M if there exist 1 <= i 1 < i 2 < . . . < i N <= M such that S j = A ij for all 1 <= j <= N , and S j < S j+1 for all 1 <= j < N .
Input
Each sequence is described with M — its length (1 <= M <= 500) and M integer numbers A i (-2 31 <= A i < 2 31 ) — the sequence itself.
Output
On the first line of the output file print L — the length of the greatest common increasing subsequence of both sequences. On the second line print the subsequence itself. If there are several possible answers, output any of them.
Sample Input
5
1 4 2 5 -12
4
-12 1 2 4
Sample Output
2
1 4
题意：求最长公共上升子序列，记录方案，任意输出。
这道题转移部分的优化告诉我们，在实现状态转移方程时，要注意观察决策集合的范围随着状态变化情况。对于
决策集合中的元素只增多不减少的情景，就可以像本题一样维护一个变量来记录决策集合的当前信息，避免重复扫描，
把转移的复杂度降低一个量级。
F（i，j）表示a序列和b序列，其中a1—ai与b1—bj以bj结尾的LCIS的长度。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define ll long long
#define llu unsigned long long
using namespace std;
const int maxn=550;
int dp[maxn][maxn];
int wa[maxn][maxn];
int a[maxn],b[maxn];
int n,m;

void print(int i,int j)
{
    for(;i;i--)
    {
        if(wa[i][j]!=-1)
        {
            print(i-1,wa[i][j]);
            printf("%d ",b[j]);
            return ;
        }
    }
    return ;
}


int main(void)
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&b[i]);
        }

        memset(dp,0,sizeof(dp));
        memset(wa,-1,sizeof(wa));

        for(int i=1;i<=n;i++)
        {
            int maxx=0;
            for(int j=1;j<=m;j++)
            {
                if(a[i]==b[j]) dp[i][j]=dp[i-1][maxx]+1,wa[i][j]=maxx;
                else dp[i][j]=dp[i-1][j];

                if(b[j]<a[i]&&dp[i-1][j]>dp[i-1][maxx]) maxx=j;
            }

        }
        int maxx=0;
        for(int i=1;i<=m;i++) if(dp[n][i]>dp[n][maxx]) maxx=i;

        printf("%d\n",dp[n][maxx]);
        print(n,maxx);
        putchar('\n');


    }
    return 0;
}