描述
中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出N匹马，每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢取最多的钱？
输入格式
第一行为一个正整数n (n <= 1000) ，表示双方马的数量。
第二行有N个整数表示田忌的马的速度。
第三行的N个整数为齐王的马的速度。
第二行有N个整数表示田忌的马的速度。
第三行的N个整数为齐王的马的速度。
输出格式
仅有一行，为田忌赛马可能赢得的最多的钱，结果有可能为负。
测试样例1
输入
3
92 83 71
95 87 74
输出
200
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 1<<30
using namespace std; bool cmp(int i,int j){
return i>j;
} int N,f[][],a[],b[],c[][]; int main(){
// freopen("01.txt","r",stdin); for(int i=;i<=N;i++)
for(int j=;j<=N;j++)
f[i][j]=-INF; scanf("%d",&N);//田忌a 齐王b
for(int i=;i<=N;i++) scanf("%d",&a[i]);
for(int i=;i<=N;i++) scanf("%d",&b[i]); sort(a+,a+N+,cmp);
sort(b+,b+N+,cmp); for(int i=;i<=N;i++){//田忌i 齐王j
for(int j=;j<=N;j++){
if(a[i]>b[j]) c[i][j]=;
else if(a[i]<b[j]) c[i][j]=-;
else c[i][j]=;
}
} f[][]=; for(int i=;i<=N;i++){//代表共比赛i次，田忌前面取了j头 ,田忌后面取了（i-j）头
for(int j=;j<=i;j++){
if(j>=)f[i][j]=max( f[i-][j] + c[N-(i-j)+][i] , f[i-][j-] + c[j][i] );
else f[i][j]= f[i-][j] + c[N-(i-j)+][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=; for(int i=;i<=N;i++) ans=max(f[N][i],ans); printf("%d\n",ans*);
return ;
}之前看别人方程理解错了，然后就没有然后了，以下是引用的题解
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即可。