田忌赛马问题

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

算法思想

先排序，齐王的马的速度放在数组a中，田忌的马的速度放在数组b中。本问题应用的算法是动态规划和贪心算法相结合解决的。从两人的最弱的马入手：

若田忌的马快，就让这两匹马比赛；

若田忌的马慢，干脆就让他对付齐王最快的马；

若两匹马的速度相等，这时有两种选择方案，或者它俩比赛，或者对付齐王最快的马。 定义子问题：l(i，j)为齐王的从第i匹马开始的j匹马与田忌的最快的j匹马比赛，田忌所获得的最大收益。

l(i,j1)当a[ij1]b[j1]时则：l(i,j)max{l(i1,j1),l(i,j1)}当a[ij1]＝b[j1]时

l(i1,j1)当a[ij1]b[j1]时程序具体实现时，为了适合c数据从0开始，稍加变动，定义子问题：l(i，j)为齐王

的从第i匹马开始到第i＋j匹马共j+1匹马与田忌的最快的j+1匹马比赛，田忌所获得的最大收益。初始化时：l[i][0]表示齐王的第i匹马与田忌最快的马比赛的结果。

二 程序源代码

#include<>

void readdata(); void init();

int N,n,a[100],b[100],l[100][100]; void main() {

int i,j,k;

scanf(\"%d\测试例子得个数 for(k=0;kreaddata(); init();

for(i=n-2;i>=0;i--) for(j=1;jl[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];

printf(\"%d\\n\ } }

void readdata() {

int i;

scanf(\"%d\马的个数：- for(i=0;iscanf(\"%d\每只马的速度； for(i=0;iscanf(\"%d\每只马的速度； }

int* qsort(int a[100],int n)//对输入的马的速度的无序序列进行排序 {

int i,j,t;

for(i=0;ifor(j=i+1;j{t=a[i];a[i]=a[j];a[j]=t;} // for(i=0;ivoid init() {

int i;

qsort(a,n); qsort(b,n);

for(i=0;iif(a[i]else if(a[i]==b[0]) l[i][0]=0; else

l[i][0]=-1; } }

三 动态规划的求解方法做出总结

用动态规划解决多阶段决策问题效率是很高的，而且思路清晰简便，同时易于实现，虽