CF1939D Big Persimmon 题解

题目链接

点击打开链接

题目解法

什么神仙题/jy

先把 \(a_i\) 都 \(\times 2\)，默认一开始先手比后手快 \(1\) 时间，可以避免两个人同时结束一个柿子的情况
朴素的 \(dp\) 是显然的，令 \(f_{l,r,det}\) 表示当前剩下区间 \([l,r]\) 中的柿子，先手比后手快了 \(det\) 秒，先手最多能比后手多吃多少体积的柿子
转移分取 \(l\) 或 \(r\)，不难做到 \(O(1)\)
暴力实现这个东西可以获得 \(56pts\)：submission

接下来的一步非常神
我们考虑使每一步的 \(det\) 都 \(\le a_{r+1}\)

1. 取左端
   这是不用管的，因为它天然满足取完之后的 \(det'\le a_{r+1}\)
2. 取右端
   我们考虑取最长的能取的后缀，假设从 \(k\) 取到 \(r\)，满足 \(0\le det-w_{k+1}-...w_{r}\le w_{k}\)
   考虑取完之后的 \(det'=w_k-(det-w_{k+1}-...-w_{r})\le w_k\)，所以每一步都能使 \(det\le a_{r+1}\)
   至于为什么一定尽可能选，是因为每次一方选择一定是选左边的一段和右边的一段，我们相当于钦定顺序为：左边的一段一个一个选，右边的一段一起选

时间复杂度 \(O(n\sum w_i)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=2010,V=20010;
int n,a[N],s[N],pos[N][V],f[N][V];
#define ff(l,r,det) f[l][(s[r]+det)/2]
int solve(int l,int r,int det){
    if(l>r) return 0;
    if(ff(l,r,det)!=-1) return ff(l,r,det);
    if(det>s[r]-s[l]) return ff(l,r,det)=s[r]-s[l-1];
    int res=-1e9;
    //choose l
    if(a[l]>det) chkmax(res,a[l]-solve(l+1,r,a[l]-det));
    else chkmax(res,a[l]+solve(l+1,r,det-a[l]));
    //choose r
    int p=pos[r][det/2];
    chkmax(res,s[r]-s[p-1]-solve(l,p-1,s[r]-s[p-1]-det));
    return ff(l,r,det)=res;
}
int main(){
    read(n);
    F(i,1,n) read(a[i]),a[i]*=2;
    F(i,1,n) s[i]=s[i-1]+a[i];
    a[n+1]=a[n];
    F(i,1,n){
        int k=i;
        for(int j=1;j<=a[i+1];j+=2){
            while(k&&j>s[i]-s[k-1]) k--;
            pos[i][j/2]=k;
        }
    }
    ms(f,-1);
    int g=solve(1,n,1),ans1=(s[n]+g)/2,ans2=(s[n]-g)/2;
    printf("%d %d\n",ans1/2,ans2/2);
    return 0;
}