[ABC303G] Bags Game 题解

· · 题解

一、题目大意

Takahashi（先手）和 Aoki（后手）在玩游戏。他们有无限的钱，从左到右一共有 N 个物品，第 i 个价值 x_i，两个人轮流操作，每次轮到的一个人可以做 3 种操作之一（假设还剩下 n 个物品）。

定义一个人的最大收益是拿到的所有东西的价值之和减去付给 Snuke 的钱数。

请问如果 2 个人都使用最优策略，使得自身的收益减去对方的收益尽量的大，那么最终 Takahashi 的收益减去 Aoki 的收益会是多少？

二、做法

部分来自官方题解。

1. 确定算法

面对这种双方轮流从一个序列两端取走物品并且要最大化自己的收益减去对方的收益的策略游戏，我们一般直接选择区间 dp。

2. 状态设计

令 f_{i,j} 表示序列里还有从第 j 个开始的 i 个物品（之所以不令 f_{i,j} 代表区间 [i,j] 是因为这样方便优化），要求此时双方都使用最优策略，最终先手减去后手的收益。我们要求的就是 f_{n,1}。

3. 状态转移

依据题意直接写。

$f_{i,j}=\max(x_j-f_{i-1,j+1},x_{i+j-1}-f_{i-1,j}) 枚举剩下 $k$ 个物品从第几个开始，这里用 $l$ 表示。方便起见，我们用 $S(i,j)$ 代表从第 $j$ 个开始的 $i$ 个物品的价值和，可以用前缀和计算。 $f_{i,j}=\max\limits_{j\le l\le j+i-k}\{S(i,j)-S(k,l)-f_{k,l}-Z\}

总时间复杂度 O(n^3)，超时。

4. 优化转移

我们可以将 (2) 的式子变成：

f_{i,j}=S(i,j)-Z-\min\limits_{j\le l\le j+i-k}\{S(k,l)+f_{k,l}\}

我们发现，对于固定的 (i,k) 这样的 [j,j+i-k] 长度是固定的。并且对于任意的 i，只有 2 种 k。所以使用单调队列，维护 S(k,l)+f_{k,l} 的最小值即可。时间复杂度 O(n^2)。

当然还有 O(n^2\log n) 的线段树、ST 表做法，以及 O(n^2) 的 O(n) RMQ 做法。

三、代码

#include<bits/stdc++.h>
#define S(p,q) s[p+q-1]-s[q-1]
#define V(p,q) (S(p,q)+f[p][q])
using namespace std;
typedef long long ll;
ll f[3010][3010],n,A,B,C,D,s[3010],x[3010],q[3010];
inline void cal(ll k,ll i,ll Z){
    for(ll j=1,h=1,t=0;j<=n+1-k;j++){
        while(h<=t&&V(k,q[t])>=V(k,j))t--;
        q[++t]=j;
        while(h<t&&q[h]<j+k-i)h++;
        if(j+k>i)f[i][j+k-i]=max(f[i][j+k-i],S(i,j+k-i)-Z-V(k,q[h]));
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>A>>B>>C>>D;
    for(ll i=1;i<=n;i++)cin>>x[i],s[i]=s[i-1]+x[i];
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n+1-i;j++)f[i][j]=max(x[j]-f[i-1][j+1],x[i+j-1]-f[i-1][j]);
        cal(i-min(i,B),i,A);cal(i-min(i,D),i,C);
    }
    cout<<f[n][1]<<'\n';
    return 0;
}