学步园

7
2 3 1 6 5 4 6
4
1 3 5 6

3
3 5 6 

5
1 2 0 2 1
3
1 0 1

2
0 1 

题意：

给你长度分别为n,m(1<=n,m<=500)的序列。要你求这两个序列的最长公共上升子序列。

思路:

最长公共子序列做过。最长上升子序列也做过。但是这题时最长公共上升子序列。。。解法肯定还是dp拉。

感觉这题的dp方程的思想很不错，体现了一种加强约束的思想。dp[i][j]表示。处理完A序列的前i个，且上升序列以B序列的B[j]结尾的最长子序列。感觉这个把状态体现以什么结尾是很不错的思想。然后转移显而易见了。

if(A[i]==B[j])

dp[i][j]=dp[i-1][k];//k是小于j且B[k]<B[j]

else

dp[i][j]=dp[i-1][j];

我们可以i,j循环这样就可以省掉找k的时间。复杂度O(n*m)

详细见代码：

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
int dp[550][550],A[550],B[550],path[550][550],n,m;
bool print(int x)
{
    if(!x)
        return false;
    if(print(path[n][x]))
        printf(" %d",B[x]);
    else
        printf("%d",B[x]);
    return true;
}
int main()
{
    int i,j,tp,ans,pos;
    while(~scanf("%d",&n))
    {
        for(i=1;i<=n;i++)
            scanf("%d",&A[i]);
        scanf("%d",&m);
        for(i=1;i<=m;i++)
            scanf("%d",&B[i]);
        memset(dp,0,sizeof dp);
        for(i=1;i<=n;i++)
        {
            tp=pos=0;
            for(j=1;j<=m;j++)
            {
                dp[i][j]=dp[i-1][j];
                path[i][j]=path[i-1][j];
                if(A[i]==B[j]&&tp+1>dp[i][j])
                    dp[i][j]=tp+1,path[i][j]=pos;
                if(B[j]<A[i]&&dp[i-1][j]>tp)
                    tp=dp[i-1][j],pos=j;
            }
        }
        ans=1;
        for(i=1;i<=m;i++)
            if(dp[n][i]>dp[n][ans])
                ans=i;
        printf("%d\n",dp[n][ans]);
        if(dp[n][ans])
            print(ans);
        printf("\n");
    }
    return 0;
}