描述

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

输入格式

第一行为一个正整数n (n <= 1000) ，表示双方马的数量。

第二行有N个整数表示田忌的马的速度。

第三行的N个整数为齐王的马的速度。

输出格式

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

测试样例1

输入

3 

92 83 71 

95 87 74

输出

200

代码

#include
      
       #include
       
         #include
        
         #include
         
          #define INF 1<<30using namespace std;bool cmp(int i,int j){    return i>j;}int N,f[3005][3005],a[3005],b[3005],c[3005][3005];int main(){//    freopen("01.txt","r",stdin);        for(int i=0;i<=N;i++)        for(int j=0;j<=N;j++)            f[i][j]=-INF;                scanf("%d",&N);//田忌a 齐王b     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++){
    //田忌i 齐王j         for(int j=1;j<=N;j++){            if(a[i]>b[j]) c[i][j]=1;            else if(a[i]
          
           =1)f[i][j]=max(  f[i-1][j]    +    c[N-(i-j)+1][i]    ,    f[i-1][j-1]    +    c[j][i] );            else    f[i][j]=      f[i-1][j]    +    c[N-(i-j)+1][i] ;                        /*    if(j>=1) f[i][j]=max(  f[i-1][j-1]  +  c[i][j]  ,  f[i-1][j]  +  c[i][N-(i-j)+1]  );             **    else     f[i][j]=                                  f[i-1][j]  +  c[i][N-(i-j)+1]   ;  //错误代码             */        }    }        int ans=0;        for(int i=0;i<=N;i++) ans=max(f[N][i],ans);        printf("%d\n",ans*200);     return 0;}
          
         
        
       
      

之前看别人方程理解错了，然后就没有然后了，以下是引用的题解

DP方程

设f[i,j]表示齐王按从强到弱的顺序出马和田忌进行了i场比赛之后，田忌从“头”取了j匹较强的马，从“尾”取了i-j匹较弱的马，所能够得到的最大盈利。

状态转移方程如下：

F[I,j]=max{f[i-1,j]+c[n-(i-j)+1,i],f[i-1,j-1]+c[j,i]}

其中c[i,j]表示田忌的马和齐王的马分别按照由强到弱的顺序排序之后，田忌的第i匹马和齐王的第j匹马赛跑所能取得的盈利，胜为1，输为－1，平为0。

结果用最大的乘以200即可。