poj2287 Tian Ji -- The Horse Racing

传送门

分析

这个题和传统的田忌赛马不一样的地方就是多了平局情况，所有我们不难想到要用dp。我们先将两人的马均降序排列，用dpij表示考虑前i匹马，田忌有几匹马是按从大到小的顺序从头取的（剩下的是从尾部取的）。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

#define sp cout<<"---------------------------------------------------"<<endl;

int dp[][],a[],b[];

inline bool cmp(int x,int y){

      return x>y;

}

inline int c(int x,int y){

      if(x>y)return ;

        else if(x<y)return -;

      return ;

}

int main(){

      int n,i,j;

      scanf("%d",&n);

      while(n!=){

        memset(dp,,sizeof(dp));

        for(i=;i<=n;i++)scanf("%d",&a[i]);

        for(i=;i<=n;i++)scanf("%d",&b[i]);

        sort(a+,a+n+,cmp);

        sort(b+,b+n+,cmp);

        for(i=;i<=n;i++){

          for(j=;j<i;j++)

            dp[i][j]=max(dp[i-][j-]+c(a[j],b[i]),dp[i-][j]+c(a[n-(i-j-)],b[i]));

          dp[i][]=dp[i-][]+c(a[n-i+],b[i]);

          dp[i][i]=dp[i-][i-]+c(a[i],b[i]);

        }

        int ans=-;

        for(i=;i<=n;i++)

          ans=max(ans,dp[n][i]);

        printf("%d\n",ans);

        scanf("%d",&n);

      }

      return ;

}