Tyvj_p1048_田忌赛马1
需积分: 0 48 浏览量
2022-08-03
18:44:16
上传
评论
收藏 172KB PDF 举报
Tyvj p1048 田忌赛马
解题报告：
首先看到这道题 ， 大部分人应该是没有思路的 ， 但熟知历史故事的人可能会想到贪心策
略 。 贪心规则如下 ： 将最双方的马排序 ， 如果自己最强的马还拼不过对方 ， 就用最弱的马输
掉 。 这个贪心策略乍一看上去是对的 ， 但经过自己的数据可以看出 ， 这个贪心策略没有考虑
到如果存在打平该怎么办。一旦出现可以打平的情况，则会导致两种分支，要不是打平 ， 要
不然为了以后得分更高此时输掉 。 。
不过 ， 这个贪心策略倒是提醒我们可以使用动态规划进行求解 ， 虽然齐王进行比赛出马
的实力是不确定的 ， 但是我们仍然可以通过排序使其有序化 ， 强制齐王按照马的实力从大到
小进行出马 。 而根据贪心 ， 我们每次可以从同样经过排序后的田忌的赛马顺序的最左端或最
右端出马，每次出完马后算出所有的情况，供后面调用（满足最有子结构性质且无后效性 ）
则方程如下：
⎪
⎭
⎪
⎬
⎫
⎪
⎩
⎪
⎨
⎧
==+−−
<<+−+−+−−
==−+−
=
i)(j ),(]1,1[
i)j(0 ),(],1[),,(]1,1[max(
0)(j ),(]0 ,1[
],[
iicompare iiF
ijincompare jiFijcompare jiF
iincompareiF
jiF
）
F[i,j] 表示在第 i 轮比赛中田忌已经从最右端（最大的马的地方）选取了 j 匹马，从最左端选
取了 n-i+j 匹马时的最大奖金。
其中，当 j==0||j==i 时需要特判（贡献 1wa ）
代码如下：
#include "iostream"
#include "cstring"
#include "cstdio"
#include "cstdlib"
评论0