#include <stdio.h>
#include <string.h>
int s1[510];
int s2[510];
int stk[510];
int vc[510][510];
int dp[510][510];
int min[510][510];
int main()
{
    int n1,n2,top,i,j,k;
    while(scanf("%d",&n1)!=EOF)
    {
        for(i=1;i<=n1;i++) scanf("%d",&s1[i]);
        scanf("%d",&n2);
        for(i=1;i<=n2;i++) scanf("%d",&s2[i]);
        for(i=0;i<=n2;i++) dp[0][i]=0;
        for(i=0;i<=n1;i++) dp[i][0]=0;
        memset(vc,0,sizeof(vc));
        for(i=1;i<=n1;i++)
        {
            for(j=1;j<=n2;j++)
            {
                dp[i][j]=dp[i-1][j-1],min[i][j]=min[i-1][j-1];
                for(k=i;k>=1;k--)
                {
                    if(s1[k]==s2[j]&&(dp[k-1][j-1]==0||min[k-1][j-1]<s2[j]))
                    {
                        if(dp[k-1][j-1]+1>dp[i][j])
                        {
                            dp[i][j]=dp[k-1][j-1]+1;
                            min[i][j]=s2[j];
                            vc[i][j]=k;
                        }
                        else if(dp[k-1][j-1]+1==dp[i][j]&&s2[j]<min[i][j])
                        {
                            min[i][j]=s2[j];
                            vc[i][j]=k;
                        }
                    }
                }
                for(k=j;k>=1;k--)
                {
                    if(s1[i]==s2[k]&&(dp[i-1][k-1]==0||min[i-1][k-1]<s1[i]))
                    {
                        if(dp[i-1][k-1]+1>dp[i][j])
                        {
                            dp[i][j]=dp[i-1][k-1]+1;
                            min[i][j]=s1[i];
                            vc[i][j]=-k;
                        }
                        else if(dp[i-1][k-1]+1==dp[i][j]&&s1[i]<min[i][j])
                        {
                            min[i][j]=s1[j];
                            vc[i][j]=-k;
                        }
                    }
                }
            }
        }
        printf("%d\n",dp[n1][n2]);
        top=0;
        while(n1>=1&&n2>=1)
        {
            if(vc[n1][n2]==0) n1--,n2--;
            else if(vc[n1][n2]>0)
            {
                stk[top++]=s2[n2];
                n1=vc[n1][n2]-1,n2--;
            }
            else
            {
                stk[top++]=s1[n1];
                n2=-vc[n1][n2]-1,n1--;
            }
        }
        for(i=top-1;i>0;i--) printf("%d ",stk[i]);
        printf("%d\n",stk[0]);
    }
    return 0;
}
    

• Re:那位大虾给一个数据，谢谢！ (22) number 2006-07-13 21:10:26