比赛 20110928 评测结果 AWWAWWAAAA
题目名称 交错匹配 最终得分 60
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-09-28 20:18:18
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

int up[210], down[210], f[210][210];

#define MAX(A,B) ((A)>=(B)?(A):(B))

int main ()
{
    freopen("crossa.in", "r", stdin);
    freopen("crossa.out", "w", stdout);

    int N, M;
    scanf("%d%d", &N, &M);

    for (int i=1; i<=N; i++)
        scanf("%d", up+i);
    for (int i=1; i<=M; i++)
        scanf("%d", down+i);

    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++)
        {
            f[i][j] = MAX(f[i-1][j], f[i][j-1]);
            if (up[i] != down[j])
            {
                for (int di=i-1; di>0; di--)
                    for (int dj=j-1; dj>0; dj--)
                        if (up[di] == down[j] && up[i] == down[dj] &&
                                f[di][dj]+2 > f[i][j])
                            f[i][j] = f[di][dj] + 2;
            }
        }

    printf("%d\n", f[N][M]);

    return 0;
}