zoj2432.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <algorithm>
using namespace std;

int l1, l2;
int a[510], b[510];
int f[510][510], pre[510][510];
int ans[510];

int main(){
    scanf("%d", &l1);
    for (int i = 1; i <= l1; i++) scanf("%d", a + i);
    scanf("%d", &l2);
    for (int i = 1; i <= l2; i++) scanf("%d", b + i);
    memset(f, 0, sizeof(f));
    memset(pre, 0, sizeof(pre));
    for (int i = 1; i <= l1; i++){
        int k = 0;
//        memcpy(pre[i], pre[i-1], sizeof(pre[i]));
        for (int j = 1; j <= l2; j++) pre[i][j] = pre[i-1][j];
        for (int j = 1; j <= l2; j++){
            f[i][j] = f[i-1][j];
            if (a[i] > b[j] && f[i][k] < f[i][j]) k = j;
            if (a[i] == b[j] && f[i][k] + 1 > f[i][j]) {
                f[i][j] = f[i][k] + 1;   
                pre[i][j] = i * (l2 + 1) + k;
            }
        }
    }
    int tmax = 0;
    for (int i = 1; i <= l2; i++)
        if (f[l1][i] > f[l1][tmax]) tmax = i;
    printf("%d\n", f[l1][tmax]);
    if (f[l1][tmax] == 0) puts(""); 
    for (int i = l1*l2 + l1 + tmax , j = f[l1][tmax]; j > 0; i = pre[i/(l2+1)][i%(l2+1)], j--)
        ans[j] = b[i%(l2+1)];
    for (int i = 1; i <= f[l1][tmax]; i++){
        printf("%d", ans[i]);
        if (i == f[l1][tmax]) puts(""); else putchar(' ');
    }
//    system("pause");
    return 0;   
}