| ||||||||||
| 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