Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
这题 我真的 不懂勒```0(N^2) 的 算法 哪错勒 ?#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator