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

## WA到吐了……各位看看怎么回事吧，用的复杂度O(nm)的算法

Posted by jeremy1022 at 2013-09-14 10:32:24 on Problem 2127
```#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: