第七届省赛赛前交流赛部分题解

a题： yougth‘s game[Ⅲ]（ 区间dp ）

这是在省赛前热身赛出的题目，可能是题目中有用到博弈的思想，很多人都在做，而且在尝试暴力。但是没有人往dp的方向上想。

<dd></dd>

<dl></dl>

<dt>题目类型：动态规划+博弈</dt>

<dt>分析：题意描述的很清楚，就是选择在两端取数，当前取的数不仅能够影响下一次的结果，而且能够影响后面的结果。。。又是一个求最优值，那么是不是可以往dp的方向上想了。区间dp</dt>

<dt>定义状态dp[ i ] [ j ] 为从 i 到 j 上a的得分，那么b的得分就是sum（i,j）-dp[ i ] [ j ]</dt>

<dt>转移方程 : dp[i][j]=max(dp[i][j],a[i]+(sum[j]-sum[i]-dp[i+1][j]));</dt>

表示区间i--j取第一个

<dt>dp[i][j]=max(dp[i][j],a[j]+(b[j-1]-b[i-1]-dp[i][j-1]));</dt>

表示区间i--j取最后一个

<dt></dt>

代码：

e：yougth‘s game[ii]

题目类型：组合博弈   

其实就是一个sg函数，sg函数讲解：

分析：题目可以抽象成一个取石子游戏，三堆石子x，y，x*y，那么就抽象成了经典的取石子游戏。

每次可以取得数目是给定的，谁最后取完谁赢。

求出三个数的sg值，然后异或就是ans

h题：合并游戏

题目类型：状态压缩动态规划

分析：给出每两个石子合并蹦出的金币，求所有石子合并之后蹦出的金币，分析可以发现不同的合并顺序会有不一样的结果，然后满足最优子结构的性质，那就是确定某几个石子合并的到的最大金币永远是确定的，那么我们可以用dp来求解，而这个题目恰好是一个从0到所有合并的一个过程，用二进制压缩来表示状态。

定义状态：dp【st】表示状态st中为1的合并起来的最大值

状态转移方程：dp[state+(1&lt;&lt;j)]=max(dp[state+(1&lt;&lt;j)], dp[state]+a[i][j]);（每次都从 i 为1的点转移过来）