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

这题 我真的 不懂勒```0(N^2) 的 算法 哪错勒 ?

Posted by __sunshine at 2009-05-11 19:31:52 on Problem 2127
#include <cstdlib>
#include <iostream>
#define  MAXN 510

using namespace std;
int an[MAXN],bn[MAXN],hash[MAXN],dp[MAXN];
int m,n;

void print(int a){
     if(a==0)return ;
     print(hash[a]);
     printf("%d ",bn[a]);
     
}


int main(int argc, char *argv[])
{
    while(scanf("%d",&m)!=EOF){
            memset(an,0,sizeof(an));
            memset(bn,0,sizeof(bn));
            for(int i=1;i<=m;i++){
                    scanf("%d",&an[i]);
            }
            scanf("%d",&n);
            for(int i=1;i<=n;i++){
                    scanf("%d",&bn[i]);
            }
            memset(dp,0,sizeof(dp));
            memset(hash,0,sizeof(hash));
            int k;
            for(int i=1;i<=m;i++){
                    k=0;
                    for(int j=1;j<=n;j++){
                            if(an[i]>bn[j]&&dp[k]<dp[j])k=j;
                            if(an[i]==bn[j]&&dp[j]<dp[k]+1){
                                    dp[j]=dp[k]+1;
                                    hash[j]=k;
                            }
                    }
            }
            int tamep=0,max_one=0;
            for(int i=1;i<=n;i++){
                    if(max_one<dp[i]){
                         max_one=dp[i];
                         tamep=i;
                    }
            }
            printf("%d\n",max_one);
            print(tamep);
            printf("\n");
    }
            
    //system("PAUSE");
    return EXIT_SUCCESS;
}

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