Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

help!!!!!!!!!!!!!!!!!!

Posted by shhu at 2007-09-07 15:56:14 on Problem 2127
#include<cstdio>
#include<cstring>
int A[512],B[512],F[512][512],pre[512][512];
void DFS(int maxi,int maxj)
{
    if(!maxj)
        return;    
    DFS(maxi-1,pre[maxi][maxj]);
    printf("%d ",B[maxj]);
}
int main()
{
    int i,j,LA,LB,k,maxi,maxj;
    while(scanf("%d",&LA)!=EOF)
    {
        for(i=1;i<=LA;i++)
            scanf("%d",A+i);
        scanf("%d",&LB);
        for(i=1;i<=LB;i++)
            scanf("%d",B+i);
        memset(F,0,sizeof(F));
        memset(pre,0,sizeof(pre));
        for(i=1;i<=LA;i++)
        {
            k=0;
            for(j=1;j<=LB;j++)
            {
                F[i][j]=F[i-1][j];
                pre[i][j]=pre[i-1][j];
                if(B[j]<A[i]&&F[i][j]>F[i][k])
                    k=j;
                if(B[j]==A[i]&&F[i][j]<F[i][k]+1)
                {
                    F[i][j]=F[i][k]+1;
                    pre[i][j]=k;
                }
          //      printf("%d %d   ",F[i][j],pre[i][j]);
            }
      //      printf("\n");
        }
        maxi=maxj=0;
        for(i=1;i<=LA;i++)
            for(j=1;j<=LB;j++)
                if(F[i][j]>F[maxi][maxj])
                    maxi=i,maxj=j;
        printf("%d\n",F[maxi][maxj]);
        if(F[maxi][maxj])
        {
            DFS(maxi-1,pre[maxi][maxj]);
            printf("%d\n",B[maxj]);
        }
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator