题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1052

解题思路

雨巨讲的思路：
区间dp。
记田忌为a，齐王为b。
将两人的马从大到小排序。
dp[i][j]表示a的从i到j匹马，与b的从n-j+i匹马到n匹马比赛的净胜数。
judge(i,j)表示的是判断a的第i匹马与b的第j匹马的大小关系。
雨巨视频55min

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1005;
int dp[N][N];
int n,a[N],b[N];

bool cmp(int x,int y)
{
    return x>y;
}

int judge(int x,int y)
{
    return a[x]>b[y]?1:a[x]==b[y]?0:-1;
}

int main()
{
    while(~scanf("%d",&n))
    {
        if(n==0) break;
        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++) scanf("%d",&b[i]);

        sort(a+1,a+n+1,cmp);
        sort(b+1,b+n+1,cmp);
        for(int i=1;i<=n;i++) dp[i][i]=judge(i,n);//初始化
        for(int len=1;len<=n;len++)
        for(int i=1;i<=n;i++)
        {
            int j=len+i-1;
            dp[i][j]=max(dp[i+1][j]+judge(i,n-j+i),dp[i][j-1]+judge(j,n-j+i));
        }
        printf("%d\n",dp[1][n]*200);
    }
}