题解：CF729F Financiers Game

· · 题解

吐槽一下怎么题解一个二个全都是哈希状态加记搜啊。

首先是动态规划。设 f_{l,r,k,0/1}，l,r 分别为先手选左边、后手选右边选了多少个，k 即为当前的 k 值，0/1 表示现在应该由先手还是后手操作，0 为先手，1 为后手。初始设所有 f_{l,r,k,0}=-\inf,f_{l,r,k,1}=\inf。

然后博弈不是很好正着 dp，考虑倒着 dp。如果 l+r\leq n 且 l+r+k>n，那么这就是一个合法的结束状态，此时 f_{l,r,k,0}=f_{l,r,k,1}=0。倒着操作中，每次将 l/r 减去 k，然后 k 可减可不减。具体地：

(f_{l,r,k,0}-\sum_{i=n-r+1}^{n-r+k}a_i)\stackrel{\min}{\longrightarrow} \begin{cases} f_{l,r-k,k,1}\\ f_{l,r-k,k-1,1} \end{cases} (r\geq k) \\ (f_{l,r,k,1}+\sum_{i=l-k+1}^{l}a_i)\stackrel{\max}{\longrightarrow} \begin{cases} f_{l-k,r,k,0}\\ f_{l-k,r,k-1,0} \end{cases} (l\geq k)

这里有 n^3 的代码。

#define rep(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define per(i,r,l) for(int i=(r),i##end=(l);i>=i##end;--i)
const int maxn=300+10;

int n,a[maxn],qa[maxn],f[2][maxn][maxn][maxn];

cin>>n;
rep(i,1,n) cin>>a[i],qa[i]=qa[i-1]+a[i];
rep(l,0,n) rep(r,0,n-l){
  rep(k,1,n-l-r) f[0][l][r][k]=-inf,f[1][l][r][k]=inf;
  rep(k,n-l-r+1,n) f[0][l][r][k]=0,f[1][l][r][k]=0;
}
per(l,n,0) per(r,n-l,0) rep(k,1,n){
  if(f[0][l][r][k]!=-inf&&r>=k) f[1][l][r-k][k]=min(f[1][l][r-k][k],f[0][l][r][k]-qa[n-r+k]+qa[n-r]),
  f[1][l][r-k][k-1]=min(f[1][l][r-k][k-1],f[0][l][r][k]-qa[n-r+k]+qa[n-r]);
  if(f[1][l][r][k]!=inf&&l>=k) f[0][l-k][r][k]=max(f[0][l-k][r][k],f[1][l][r][k]+qa[l]-qa[l-k]),
  f[0][l-k][r][k-1]=max(f[0][l-k][r][k-1],f[1][l][r][k]+qa[l]-qa[l-k]);
}
cout<<f[0][0][0][1];

注意到实际有用的 k 只有 \Theta(\sqrt{n}) 级别，因为原问题中每次取 k 个数后 k 可增加 1 可不增加，也就是取的数量是 \Theta(k^2) 量级的。而取的数量又有一个上界 n，所以 k 有 \Theta(\sqrt{n}) 的上界。

到这里和其他题解大致相同。但是接下来就看不懂了。其他题解是怎么哈希怎么记搜然后哒哒哒。

目前我们空间和时间都是 n^3。

但是实际上可以把 k 这一维拿到最前面，然后滚动数组，这样空间就优化到了 n^2。k 有上限，然后时间优化到了 \Theta(n^2 \sqrt{n})。

又有 r-l 也是 \sqrt{n} 量级的。因为原题中每个回合两人取数的数量之差最多也就为 1，且最多取 \sqrt{n} 轮，所以 r-l 的量级也是 \Theta(\sqrt{n})。

实际写代码中，k 和 |r-l| 可以从 100 开始枚举。从 89 或更低开始枚举可能会 WA，因为 k 的最大值 k_{\max} 要满足 \frac{k_{\max}\times(1+k_{\max})}{2}\geq n=4000，解得 k_{\max}\geq 90，所以枚举的下界是 90，但是稍微超一点应该也没啥关系。

这样时间就优化到了 \Theta(n^2)。

然后也没啥记搜或状态哈希存储的必要。

代码：

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
#define rep(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define per(i,r,l) for(int i=(r),i##end=(l);i>=i##end;--i)
#define ll long long
#define int ll
#define double long double
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define popcnt __builtin_popcount
#define rbtree(way) tree<way,null_type,less<way>,rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
class IO{
    char ibuf[1<<16],obuf[1<<16],*ipl=ibuf,*ipr=ibuf,*op=obuf;
    public:
    ~IO(){write();}
    inline void read(){ipl==ipr?ipr=(ipl=ibuf)+fread(ibuf,1,1<<15,stdin):0;}
    inline void write(){fwrite(obuf,1,op-obuf,stdout),op=obuf;}
    inline char getchar(){return (read(),ipl!=ipr)?*ipl++:EOF;}
    inline void putchar(char c){*op++=c;if(op-obuf>(1<<15)) write();}
    template<typename V>IO&operator>>(V&v){
        int s=1;char c=getchar();v=0;
        for(;!isdigit(c);c=getchar()) if(c=='-') s=-s;
        for(;isdigit(c);c=getchar()) v=(v<<1)+(v<<3)+(c^48);
        return v*=s,*this;
    }
    inline IO&operator<<(char c){return putchar(c),*this;}
    template<typename V>IO&operator<<(V v){
        if(!v) putchar('0');if(v<0) putchar('-'),v=-v;
        char stk[100],*top=stk;
        for(;v;v/=10) *++top=v%10+'0';
        while(top!=stk) putchar(*top--);return *this;
    }
}io;
//#define cin io
//#define cout io
#define Tie (ios::sync_with_stdio(0),cin.tie(0),cout.tie(0))
const int maxn=4e3+10,maxm=1e6+10,mod=998244353,inf=1e18;
inline int ksm(int x,int k,int mod=mod){
    int ans=1;
    for(x%=mod;k;k>>=1,x=x*x%mod) if(k&1) ans=ans*x%mod;
    return ans;
}

int n,a[maxn],qa[maxn],f[2][2][maxn][maxn];

signed main(){
    Tie;
    cin>>n;
    rep(i,1,n) cin>>a[i],qa[i]=qa[i-1]+a[i];
    rep(l,0,n-100) rep(r,0,n-100-l) f[0][0][l][r]=-inf,f[1][0][l][r]=inf;
    per(k,100,1){
        rep(l,0,n-k+1) rep(r,max(0ll,l-100),min(l+100,n-k-l+1))
            f[0][k-1&1][l][r]=-inf,f[1][k-1&1][l][r]=inf;
        per(l,n,0) per(r,min(l+100,n-l),max(0ll,l-100)){
            if(f[0][k&1][l][r]!=-inf&&r>=k)
                f[1][k&1][l][r-k]=min(f[1][k&1][l][r-k],f[0][k&1][l][r]-qa[n-r+k]+qa[n-r]),
                f[1][k-1&1][l][r-k]=min(f[1][k-1&1][l][r-k],f[0][k&1][l][r]-qa[n-r+k]+qa[n-r]);
            if(f[1][k&1][l][r]!=inf&&l>=k)
                f[0][k&1][l-k][r]=max(f[0][k&1][l-k][r],f[1][k&1][l][r]+qa[l]-qa[l-k]),
                f[0][k-1&1][l-k][r]=max(f[0][k-1&1][l-k][r],f[1][k&1][l][r]+qa[l]-qa[l-k]);
        }
    }
    cout<<f[0][1][0][0];
    return 0;
}