tianjisaima.txt

田忌赛马

12． *田忌赛马 
田忌与齐王赛马，双方各有n匹马参赛（n<=100），每场比赛赌注为1两黄金，现已知齐王与田忌的每匹马的速度，并且齐王肯定是按马的速度从快到慢出场，现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金（输用负数表示）。 
分析：先排序，齐王的马的速度放在数组a中，田忌的马的速度放在数组b中。本问题应用的算法是动态规划和贪心算法相结合解决的。从两人的最弱的马入手： 
若田忌的马快，就让这两匹马比赛； 
若田忌的马慢，干脆就让他对付齐王最快的马； 
若两匹马的速度相等，这时有两种选择方案，或者它俩比赛，或者对付齐王最快的马。 
定义子问题：l(i，j)为齐王的从第i匹马开始的j匹马与田忌的最快的j匹马比赛，田忌所获得的最大收益。 
则： 
程序具体实现时，为了适合c数据从0开始，稍加变动，定义子问题：l(i，j)为齐王的从第i匹马开始到第i＋j匹马共j+1匹马与田忌的最快的j+1匹马比赛，田忌所获得的最大收益。初始化时：l[i][0]表示齐王的第i匹马与田忌最快的马比赛的结果。 
程序如下： 
#include<stdio.h> 
void readdata(); 
void init(); 
int n,a[100],b[100],l[100][100]; 
int 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]; 
printf("%d",l[0][n-1]); 
} 
void readdata() 
{ 
int i; 
scanf("%d",&n); 
for(i=0;i<n;i++) 
scanf("%d",&a[i]); 
for(i=0;i<n;i++) 
scanf("%d",&b[i]); 
} 
void init() 
{ 
int i; 
// qsort(a,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; 
} 
}