原题链接：P2734 游戏 A Game
本题的大体思路是很明确的，初见有点Nim游戏的意思（当然似乎也能用博弈论搞，只是我太弱了，区间DP都要写一下午），审过之后发现是个比较容易想到的区间dp，只是我的方程似乎和题解的不太一样。
这道题有一点非常迷，就是你初见很难看懂它想让你干什么，一旦审错就会GG，收不了。这可能是翻译的锅，毕竟原题出自USACO，洛谷评级为绿题（普及+/提高），我觉得比较客观。
看一下题目中的描述：
编一个执行最优策略的程序，最优策略就是使玩家在与最好的对手对弈时，能得到的在当前情况下最大的可能的总分的策略。你的程序要始终为第二位玩家执行最优策略。
哦豁，完蛋，本来你不说可能能看懂的说了也开始迷了。
其实它的意思就是两边都执行最优策略，也就是Nim的搞法。为什么呢？最优策略定义为使玩家在与最好的对手对弈时，能得到的在当前情况下最大的可能的总分的策略，保证了对手策略最优，因为要与“最好的对手”对弈，肯定对方不可能放水，而“为第二位玩家执行最优策略”则意味着第二位也不能随便乱骚，这样一来我们的方向就确定了：双方都执行全局最优解。
有了切入点之后，稍作分析不难发现：设f[i][j]为第一个游戏者在闭区间[i,j]中所能得到的最大得分，则状态转移方程可表示为：f[i][j]=(((j-i)&1)==!ep)?max(f[i+1][j]+a[i],f[i][j-1]+a[j]):min(f[i+1][j],f[i][j-1])
其中ep=N&1已事先计算好，且在整个过程中不改变。
简单解释一下，ep是我设置的一个奇偶标志，因为如果按照我的思路设计状态，N的奇偶势必会对f[i][j]的计算造成影响，若N为奇数即ep=N&1=1，则对于每个区间长度j-i+1为奇数的状态，均是第一个游戏者取数的状态，而区间长度为偶数则是第二个游戏者取数，无需进行累加（想一想，为什么？）。
另外，上述状态转移方程其实是化简后的结果，所以有必要进行详细说明。参考下面这个dp函数：
int dp(int i,int j){
if(i==j)return ep?sum(i,i):0;
if(f[i][j])return f[i][j];
if(((j-i)&1)==!ep){//第一个游戏者取数
//为什么必须是"==!ep"？
//"==ep"有什么问题呢？
//因为(j-i)并不是闭区间[i,j]的长度，(j-i+1)才是。若写作"((j-i+1)&1)==ep"，那么这个条件将会是正确的。
f[i][j]=max(dp(i+1,j)+sum(i,i),dp(i,j-1)+sum(j,j));
}else{//第二个游戏者取数
//他们都取全局最优解，所以进行计算。
int l=dp(i+1,j),r=dp(i,j-1);
//int ss=sum(i,j); 假设ss为闭区间[i,j]的总和，l和r分别为[i+1,j]和[i,j-1]中第一个游戏者的最大得分
if(l<r){//ss-l>ss-r 显见，总和-其中一个得分=另一个的得分，因为数必须取完，化简得min(dp(i+1,j),dp(i,j-1))
f[i][j]=l;
}else{
f[i][j]=r;
}
}
return f[i][j];
}参考代码注释中的分析，得到简化后的dp函数：
int dp(int i,int j){
if(i==j)return ep?a[i]:0;//*important
if(f[i][j])return f[i][j];
return f[i][j]=(((j-i)&1)==!ep)?max(dp(i+1,j)+a[i],dp(i,j-1)+a[j]):min(dp(i+1,j),dp(i,j-1));
}简洁优美。其中i==j的特判是为了规避初始化的窘境，这一点我没能想到更好的解决方案，需要注意。
改成递推计算：
scanf("%d",&N);
ep=N&1;//根据N的奇偶决定计算方式。
int tot=0;//存一个总和，便于计算第二个游戏者的得分。
for(register int m=1;m<=N;m++)scanf("%d",&a[m]),tot+=a[m];
//f[i][j]依赖于f[i+1][j]和f[i][j-1]，所以我们可以递推处理。
//但对每次循环a[i]与a[j]都是必须的，故无法边读边计算。
//使用滚动数组可节约空间，O(n^2)优化至O(n)。
for(register int i=N;i>=1;i--){
for(register int j=1;j<=N;j++){
if(i==j)f[j]=ep?a[i]:0;
else f[j]=(((j-i)&1)==!ep)?max(f[j]+a[i],f[j-1]+a[j]):min(f[j],f[j-1]);
}
}
printf("%d %d",f[N],tot-f[N]);就是如此简单√ ->R16029924
一个常数优化：考虑第二重循环，j根本不必从1开始枚举，因为我们规定i和j分别是区间[i,j]下界和上界，即满足$i \leq j$，j可以从i开始枚举，可以优化常数。
而且，这样一来的话，循环中的if语句也不再必要（想一想，为什么？），代码更加简洁：
for(register int i=N;i>=1;i--){
for(register int j=i;j<=N;j++){
f[j]=(((j-i)&1)==!ep)?max(f[j]+a[i],f[j-1]+a[j]):min(f[j],f[j-1]);
}
}分析i==j时的情况，此时((j-i)&1)==!ep等价于0==!ep，即条件退化为ep?(...):(...)，已知ep?a[i]:0是正确的结论，根据计算顺序，j枚举的范围[i,N]右端点固定，左端点逐渐左移，当i==j时f[j]尚未计算（因为若此时不是第一次循环，上次计算的范围是[i+1,N]；而如果此时是第一次循环的话计算尚未开始），初始化f[j]=0；i从大到小枚举，f[j]都尚未计算f[j-1]更不可能已经算过。故此时max(f[j]+a[i],f[j-1]+a[j])直接化简为max(a[i],a[j])，是同一个数a[i]；min(f[j],f[j-1])参考前面的分析可化为min(0,0)=0，此时的方程与f[j]=ep?a[i]:0等价。
版权声明：本文是原创文章，版权归 无限UCW 所有。
本文链接：https://ucw.moe/archives/solution-luogu-p2734.html
本站所有原创文章采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可。
您可以自由地转载和修改，但请务必注明文章来源并且不可用于商业目的。
