2021 ICPC Jinan C Optimal Strategy

C Optimal Strategy - 代码见此

先从游戏分析:

1、如果当前情况为:物品中最大值 A_max 的个数 C(A_max) 为奇数,那么此回合玩家是一定要拿 A_max 的,并将 C(A_max) 变为偶数传给对方。此后,单考虑值为 A_max 的物品,该玩家一定会比对手多拿一次,符合最优情况。

2、若当前物品中最大值 A_max 的个数 C(A_max) 为偶数,
显然,双方都遵循以下最优决策:
①上一轮对手拿了一次 A_max , 此回合我必须也拿A_max(如果还能拿A_max的话)。
②上一轮对手没有拿 A_max(或者C(A_max)变成零),那我可以任意拿一个物品,值随意。

然后分析计数:

我们将物品按不同值的个数存储好,并按值从小到大的顺序计算,动态规划的思想来模拟方案数

首先定义 f [ i ] 为只用小于等于 i 的元素,能构成的最优游戏方案数

为了方便理解,我们对输入的序列排一下序(代码实现不必排序)
假设某一排序后的输入为: 1 1 1 4 4 5,那么 f [ 1 ] 代表1 1 1三个元素的子序列的最优游戏方案数,同理 f [ 4 ] 代表1 1 1 4 4五个元素的子序列的最优游戏方案数。

从最优决策可得,我们将所有相同元素都两两配对,即无论哪一方拿了其中一个,下一轮玩家一定是拿另一个,则配对好的两个相同元素放在一起考虑。
那么在遍历过程中,
①假设当前处理到了所有值为 i 的元素,那么所有小于 i 的元素都不必再按两两配对考虑, 因为它们任何一个都不是此时序列中的最大值,可以任意顺序取走。
②由于是从小到大遍历,当前 i 一定比前面的都大, 那么可以随便插入到 f [ i-1 ]的任何一种方案,对应的序列中,的任何一个位置。
若 C[ i ] 为奇数, 那么一定是在序列最前面放一个 i ,然后 C[ i ] 变成了偶数,并配对成了 X = C[ i ] / 2 对, 假设 sum[ i-1 ] 是所有小于 i 的元素的总个数,那么 f [ i ] = f [ i-1 ] × C(sum[ i-1 ] + X,X)× A(C[ i ],C[ i ])

代码见此

以下是两种典例,图文结合理解更佳
请添加图片描述
请添加图片描述

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
https://docs.unity.cn/cn/2020.3/ScriptReference/IMGUI.Controls.TreeView.html

)">
下一篇>>