记录编号	37121	评测结果	AAAAAAAAAA
题目名称	田忌赛马	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.589 s
提交时间	2012-03-24 18:18:15	内存使用	0.34 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
const int N = 5010;
int n, k, s;
int a[N], b[N], f[2][N];
inline int cmp(const void *x, const void *y) {
    return *(int*)x < *(int*)y;
}
inline int win(int x, int y) {
    if(b[x] > a[y])
        return -1;
    else if(b[x] == a[y])
        return 0;
    return 1;
}
int main() {
    freopen("horsea.in", "r", stdin);
    freopen("horsea.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d", b+i);
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
    qsort(b+1, n, sizeof(int), cmp);
    qsort(a+1, n, sizeof(int), cmp);
    memset(f, 128, sizeof(f));
    s = f[0][0];
    f[0][0] = 0;
    for(int i=1; i<=n; i++) {
        k = !k;
        memset(f[k], 128, sizeof(f[k]));
        for(int j=0; j<i; j++) {
            if(f[k][j+1] < f[!k][j] + win(i, j+1))
                f[k][j+1] = f[!k][j] + win(i, j+1);
            if(f[k][j] < f[!k][j] + win(i, n-i+j+1))
                f[k][j] = f[!k][j] + win(i, n-i+j+1);
        }
    }
    for(int i=0; i<=n; i++)
        if(s < f[k][i]) s = f[k][i];
    printf("%d\n", s);
    return 0;
}