【Tyvj1048】田忌赛马

2014-03-28
竞赛题解 / 动态规划
TYVJ

描述 Description

中国古代的历史故事 “田忌赛马” 是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出 N 匹马，每场比赛，输的一方将要给赢的一方 200 两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢取最多的钱？

输入格式 InputFormat

第一行为一个正整数 n (n <= 1000) ，表示双方马的数量。
第二行有 N 个整数表示田忌的马的速度。
第三行的 N 个整数为齐王的马的速度。

输出格式 OutputFormat

仅有一行，为田忌赛马可能赢得的最多的钱，结果有可能为负。

样例输入 SampleInput

7
9 8 7 6 5 4 2
9 8 7 6 5 4 3

样例输出 SampleOutput

1000

注释 Hint

二分图匹配会超时，正解是贪心策略 + 线性动规。

Tyvj 1048

代码 Code

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a[2000],b[2000];
int f[1001][1001];
int i,j,t,n,m,l,r,k,z,y,x;
int diff(int x,int y)
{
    if (a[x]>b[y]) return 200;
    if (a[x]<b[y]) return -200;
    return 0;
}
bool comp(int x,int y)
{
    return x>y;
}
int main()
{
    memset(f,0,sizeof(f));
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    for (i=1;i<=n;i++) scanf("%d",&b[i]);
    sort(a+1,a+n+1,comp);
    sort(b+1,b+n+1,comp);
    for (i=1;i<=n;i++) for (j=0;j<=i;j++)
    {
        f[i][j]=(j>0)?max(f[i-1][j]+diff(n-(i-j)+1,i),f[i-1][j-1]+diff(j,i)):f[i-1][j]+diff(n-(i-j)+1,i);
    }
    z=0;
    for (i=1;i<=n;i++) z=max(z,f[n][i]);
    printf("%d\n",z);
    return 0;
}