| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3071 人关注过本帖, 1 人收藏
标题:田忌赛马
取消只看楼主 加入收藏
无悔选择
Rank: 1
等 级:新手上路
威 望:1
帖 子:45
专家分:0
注 册:2005-12-25
收藏(1)
 问题点数:0 回复次数:1 
田忌赛马
12.*田忌赛马
田忌与齐王赛马,双方各有n匹马参赛(n<=100),每场比赛赌注为1两黄金,现已知齐王与田忌的每匹马的速度,并且齐王肯定是按马的速度从快到慢出场,现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金(输用负数表示)。
搜索更多相关主题的帖子: 田忌 赛马 黄金 速度 赌注 
2006-04-08 15:03
无悔选择
Rank: 1
等 级:新手上路
威 望:1
帖 子:45
专家分:0
注 册:2005-12-25
收藏
得分:0 
#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; //输出最后的结果
}

2006-04-08 15:03
快速回复:田忌赛马
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.012189 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved