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