题解：B4168 [GXPC-S 2024] 分糖果

StelChord · 2025-12-15 13:48:55 · 题解

此题可以用动态规划来解决。

状态设计：

注意到题面中。

对于 100\% 的数据，保证 1\le n,a_i\le 10^5。

使用一维，可以想到使用两个数组 dp1 与 dp2 ，意义如下：

• dp1[i] 表示当分配权在小林时，从第 i 包到第 n 包糖果中，小林 最终能获得的最大糖果数。

• dp2[i] 表示当分配权在小伊时，从第 i 包到第 n 包糖果中，小林 最终能获得的最大糖果数。

状态转移：

情况 1：分配权在小林。

小林可以选择：

1. 把 a_i 给自己：

   • 小林糖果增加 a_i。
   • 分配权转给小伊。
   • dp1[i] 的结果：a[i]+dp2[i+1]。

2. 把 a_i 给小伊：

   • 小林糖果不增加。
   • 分配权仍在小林。
   • dp1[i] 的结果：dp1[i+1]。

因为小林希望自己糖果最多：

dp1[i]=max(dp1[i+1],dp2[i+1]+a[i]);

情况 2：分配权在小伊。

首先，小伊希望最大化自己的糖果数，其实就是最小化小林的糖果数。

1. 小伊把 a_i 给自己：

   • 小伊糖果增加 a_i。
   • 分配权转给小林。
   • dp2[i] 的结果：dp1[i+1]。

2. 小伊把 a_i 给小林：

   • 小林糖果增加 a_i。
   • 分配权仍在小伊。
   • dp2[i] 的结果：a[i]+dp2[i+1]。

小伊会选择让小林收益最小的那个选项：

dp2[i]=min(dp1[i+1],dp2[i+1]+a[i]);

最终答案：

新增一个变量 tot 记录总糖果数。

小林的最终糖果数为 dp1[1]。

小伊的糖果数就是 tot-dp1[1]。

记得开 long long。

完整代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=100005;
int dp1[maxn],dp2[maxn],n,a[maxn],tot;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],tot+=a[i];
    for(int i=n;i>=1;i--){
        dp1[i]=max(dp1[i+1],dp2[i+1]+a[i]);
        dp2[i]=min(dp1[i+1],dp2[i+1]+a[i]);
    }
    cout<<max(dp1[1],tot-dp1[1]);
    return 0;
}