B4168 [GXPC-S 2024] 分糖果 题解
lsixuan
·
·
题解
题意：
有 n 包糖果从左到右排列，小林和小伊分糖，小林先分配。分配者可以把当前最左的糖分给自己或对方，没拿到糖的人则下一次分配糖。两人会用最优策略让自己的糖的总数尽可能多，最终求两人中糖更多的那个人糖果数量值。
分析：
一眼 dp 不用说，dp 就要考虑要状态定义和状态转移。
状态定义
$dp[1][i]$ 表示分第 $i$ 包糖且**当前为小伊分配**时，小伊能获得的最大糖数。
#### 状态转移
正着想推你会想了很久都不会转移，故考虑从后往前推，易发现第 $i$ 包的决策依赖于第 $i+1$ 包的结果。
每个人都有两种选择：
- 把第 $i$ 包糖分给自己：此时自己获得 $a[i]$，分配权转移到另一个人手中，后续能获得 $dp[1][i+1]$，总收益为 $dp[1][i+1] + a[i]$。
- 把第 $i$ 包糖分给另一个人：此时自己收益就为 $0$，但分配权仍在自己手中，后续能获得 $dp[0][i+1]$，总收益为 $dp[0][i+1]$。
因为要选择收益更大的方案，因此得转移方程：
$$
dp[0][i] = \max (dp[1][i+1] + a[i], dp[0][i+1])
$$
另一个人则获得：
$$
dp[1][i] = \min(dp[1][i+1] + a[i], dp[0][i+1])
$$
因为小林先分，所以他总能获得更多的糖（先分糖的人不可能拿的少吧），所以答案直接输出 $dp[0][i]$ 即可
---
### Code：
```c++14
#include<bits/stdc++.h>
#define int long long
#define cin std::cin
#define cout std::cout
#define endl '\n' // 宏定义
using namespace std;
const int maxn=1e5+5;
int n,a[maxn],dp[2][maxn];
signed main(){
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); // 关闭流同步提升 cin/cout 性能
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i]; // 读入
for(int i=n;i>=1;i--){
dp[0][i]=max(dp[1][i+1]+a[i],dp[0][i+1]);
dp[1][i]=min(dp[1][i+1]+a[i],dp[0][i+1]);
} // 转移
cout<<dp[0][1]<<endl;
return 0;
}
```
---
### 致谢
感谢 @[StelChord](luogu://user/1115911) 大佬对输出答案代码的优化
管理员大大辛苦了