12．*田忌赛马
田忌与齐王赛马，双方各有n匹马参赛（n<=100），每场比赛赌注为1两黄金，现已知齐王与田忌的每匹马的速度，并且齐王肯定是按马的速度从快到慢出场，现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金（输用负数表示）。

#include<iostream.h>
int n,a[100],b[100],l[100][100];
int Quicksort(int r[],int low,int high)
{
int key,t;
t=r[low];
key=r[low];
while(low<high)
{
while(low<high&&r[high]<=key)
{
--high;
}
r[low]=r[high];
while(low<high&&r[low]>=key)
{
++low;
}
r[high]=r[low];
}
r[low]=t;
return low;
}
void Qsort(int r[],int low,int high)
{
int key;
if(low<high)
{
key=Quicksort(r,low,high);
Qsort(r,low,key-1);
Qsort(r,key+1,high);
}
}
void readdata() //读入马匹的速度值
{
int i;
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
cin>>b[i];
}
void init() //初始化函数，将两组马匹降序排列
{
int i;
Qsort(a,0,n);
Qsort(b,0,n);
for(i=0;i<n;i++)
{
if(a[i]<b[0])
l[i][0]=1;
else
if(a[i]==b[0])
l[i][0]=0;
else
l[i][0]=-1;
}
}
void main()
{
int i,j;
readdata();
init();
for(i=n-2;i>=0;i--)
{
for(j=1;j<n-i;j++) //齐王和田忌都从最慢的马开始比较
{
if(a[i+j]<b[j]) //如果田忌的马快
l[i][j]=l[i][j-1]+1;//让当前的胜场加一
else
{
if(a[i+j]>b[j])//如果齐王的马快
l[i][j]=l[i+1][j-1]-1;//让当前的胜场减一
else //在两匹马速度相同时
{
if(l[i+1][j-1]-1>l[i][j-1])//如果让其对付齐王最快的马胜场相对多
l[i][j]=l[i+1][j-1]-1; //就让其对付齐王最快的马，胜场数减一
else //否则，让两匹速度相同的马比赛
l[i][j]=l[i][j-1]; //胜场数不变
}
}
}
}
cout<<l[0][n-1]<<endl; //输出最后的结果
}

最好的结果就是田忌出场次序调整后能赢最多的黄金 。
有两个想法，
1 穷举法，肯定能计算出赢最多的两黄金数。
2 研究规律
穷举就不说了。假设3匹马
王的马的速度：8 5 3
田的马的速度：7 4 1 田最多赢2场，取决于田最快马的速度，和王最慢马的速度。
王：10 8 6 4 3
田 6 5 4 3 2 田最多赢2场 。
规律 FunMax（） ----田最快马速度大于王的马速度的个数
FunMin（） ----王最慢马速度大于田的马速度的个数
赢的次数 nCount = FunMax()-FunMin() +1 ;

void ReadInfo（）; // 读两人马速到W[] 和t[]
int FunMax(int *p,int *q);
int FunMin(int *p,int *q);

void main()
{
int w[100]={0}; //王
int t[100]={0}; //田
ReadInfo();
int max = FunMax(w,t);
int min = FunMin(w,t);

printf("最多赢的黄金%d",max+min+1);

}

穷举法是不可能的,复杂度是n!