poj 2287 Tian Ji -- The Horse Racing

题目链接：http://poj.org/problem?id=2287

题目大意：田忌赛马。

题目思路：

Ø 1、如果田忌剩下的马中最强的马都赢不了齐王剩下的最强的马，那么应该用最差的一匹马去输给齐王最强的马。

Ø 2、如果田忌剩下的马中最强的马可以赢齐王剩下的最强的马，那就用这匹马去赢齐王剩下的最强的马。

Ø 3、如果田忌剩下的马中最强的马和齐王剩下的最强的马打平的话，可以选择打平或者用最差的马输掉比赛。

在第三步的时候出现选择，我们需要用dp,定义dp[i][j]为在前i场比赛中，田忌派出j匹好马所能得到的最大收益。则转移方程为dp[i][j]=max(dp[i-1][j-1]+g[j][i],dp[i-1][j]+g[n-i+j+1][i]);（因为田忌每次不是选择好马就是选择劣马）。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
inline int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
bool cmp(int a,int b)
{
    return a>b;
}
int n,num;
int a[1010],b[1010],dp[1010][1010],g[1010][1010];
int main()
{
    int i,j;
    while(scanf("%d",&n),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,cmp);
        sort(b+1,b+n+1,cmp);
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if(a[i]<b[j])
                    g[i][j]=-1;
                else if(a[i]==b[j])
                    g[i][j]=0;
                else
                    g[i][j]=1;
            }

        for(i=0;i<=n;i++)
            for(j=0;j<=n;j++)
                dp[i][j]=-inf;
        dp[0][0]=0;
        for(i=1;i<=n;i++)
            for(j=0;j<=i;j++)
            {
                if(j>=1)
                dp[i][j]=max(dp[i-1][j-1]+g[j][i],dp[i-1][j]+g[n-i+j+1][i]);
                else
                dp[i][j]=dp[i-1][j]+g[n-i+j+1][i];
            }

        int ans=-inf;
        for(i=0;i<=n;i++)
        {
            ans=max(dp[n][i],ans);
        }
        printf("%d\n",ans*200);
    }
}