| ||||||||||
| 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 | |||||||||
WA到吐了……各位看看怎么回事吧,用的复杂度O(nm)的算法#include <stdio.h>
#include <string.h>
#define MAX_LEN 500
int f[MAX_LEN + 10][MAX_LEN + 10];
int path[MAX_LEN + 10];
int a[MAX_LEN + 10], b[MAX_LEN + 10];
int output[MAX_LEN + 10];
int m1, m2;
int main(){
int i, j, max, last, start;
scanf("%d", &m1);
for(i = 1; i <= m1; i++)
scanf("%d", &a[i]);
scanf("%d", &m2);
for(j = 1; j <= m2; j++)
scanf("%d", &b[j]);
memset(f, 0, sizeof(f));
memset(path, -1, sizeof(path));
for(i = 1; i <= m1; i++){
max = 0;
last = -1;
for(j = 1; j <= m2; j++){
f[i][j] = f[i - 1][j];
if(a[i] > b[j] && f[i- 1][j] > max){
max = f[i - 1][j];
last = j;
}
if(a[i] == b[j]){
f[i][j] = max + 1;
path[j] = last;
}
}
}
max = 0;
start = 0;
for(j = 1; j <= m1; j++){
if(f[m1][j] > max){
max = f[m1][j];
start = j;
}
}
printf("%d\n", max);
int count = 0;
if(start > 0){
do{
output[max - count - 1] = b[start];
count++;
start = path[start];
}while(start != -1);
}
for(i = 0; i < max - 1; i++)
printf("%d ", output[i]);
if(i > 0)
printf("%d\n", output[i]);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator