贪心算法：田忌赛马－HDU1052 & POJ2287 & ZOJ2397

最新推荐文章于 2023-11-08 16:31:36 发布

Raise

最新推荐文章于 2023-11-08 16:31:36 发布

阅读量5.8k

点赞数 1

分类专栏： C++ ACM 算法分析与设计文章标签： acm 算法

本文链接：https://blog.csdn.net/linraise/article/details/19175801

版权

该博客介绍了一个著名的中国历史故事——田忌赛马，并将其转化为寻找最大匹配的图论问题。通过贪心算法，田忌可以最大化赢得比赛的银两。题目要求编写程序解决特殊匹配问题，根据马的速度决定比赛胜负。输入包含多组测试用例，输出田忌最多能赢得的银两数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Tian Ji -- The Horse Racing

Time Limit: 5 Seconds Memory Limit: 32768 KB

Here is a famous story in Chinese history.

"That was about 2300 years ago. General Tian Ji was a high official in the country Qi. He likes to play horse racing with the king and others."

"Both of Tian and the king have three horses in different classes, namely, regular, plus, and super. The rule is to have three rounds in a match; each of the horses must be used in one round. The winner of a single round takes two hundred silver dollars from the loser."

"Being the most powerful man in the country, the king has so nice horses that in each class his horse is better than Tian's. As a result, each time the king takes six hundred silver dollars from Tian."

"Tian Ji was not happy about that,