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 |
hmm... help meI tried but faild hmm.. this problem is LCS???? please change this source correctly.. my source is #include <stdio.h> int n, m; int a[505]; int b[505]; int dy[505][505]; int check[505][505]; void input() { int i; scanf("%d", &n); for(i=1;i<=n;i++) { scanf("%d", &a[i]); } scanf("%d", &m); for(i=1;i<=m;i++) { scanf("%d", &b[i]); } } void back(int x, int y, int cnt) { int i; if(x==0 || y==0) { return; } if(a[x]==b[y]) { back(x-1, y-1, cnt+1); printf("%d ", a[x]); } else if(dy[x-1][y]>dy[x][y-1]) { back(x-1, y, cnt); } else { back(x, y-1, cnt); } } void process() { int i, j; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(a[i]==b[j] && a[i]>check[i-1][j-1]) { dy[i][j]=dy[i-1][j-1]+1; check[i][j]=a[i]; } else { if(dy[i-1][j]>dy[i][j-1]) { dy[i][j]=dy[i-1][j]; check[i][j]=check[i-1][j]; } else { dy[i][j]=dy[i][j-1]; check[i][j]=check[i][j-1]; } } } } printf("%d\n", dy[n][m]); back(n, m, 0); } int main() { input(); process(); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator