专栏文章

题解：CF729F Financiers Game

SSTARSczyy
CF729F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mindvb8k
此快照首次捕获于
2025/12/02 00:48
3 个月前
此快照最后确认于
2025/12/02 00:48
3 个月前
查看原文
吐槽一下怎么题解一个二个全都是哈希状态加记搜啊。
首先是动态规划。设 fl,r,k,0/1f_{l,r,k,0/1}，l,rl,r 分别为先手选左边、后手选右边选了多少个，kk 即为当前的 kk 值，0/10/1 表示现在应该由先手还是后手操作，00 为先手，11 为后手。初始设所有 fl,r,k,0=−inf⁡,fl,r,k,1=inf⁡f_{l,r,k,0}=-\inf,f_{l,r,k,1}=\inf。
然后博弈不是很好正着 dp，考虑倒着 dp。如果 l+r≤nl+r\leq n 且 l+r+k>nl+r+k>n，那么这就是一个合法的结束状态，此时 fl,r,k,0=fl,r,k,1=0f_{l,r,k,0}=f_{l,r,k,1}=0。倒着操作中，每次将 l/rl/r 减去 kk，然后 kk 可减可不减。具体地：
(fl,r,k,0−∑i=n−r+1n−r+kai)⟶min⁡{fl,r−k,k,1fl,r−k,k−1,1(r≥k)(fl,r,k,1+∑i=l−k+1lai)⟶max⁡{fl−k,r,k,0fl−k,r,k−1,0(l≥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)
这里有 n3n^3 的代码。
CPP
#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];
注意到实际有用的 kk 只有 Θ(n)\Theta(\sqrt{n}) 级别，因为原问题中每次取 kk 个数后 kk 可增加 11 可不增加，也就是取的数量是 Θ(k2)\Theta(k^2) 量级的。而取的数量又有一个上界 nn，所以 kk 有 Θ(n)\Theta(\sqrt{n}) 的上界。
到这里和其他题解大致相同。但是接下来就看不懂了。其他题解是怎么哈希怎么记搜然后哒哒哒。
目前我们空间和时间都是 n3n^3。
但是实际上可以把 kk 这一维拿到最前面，然后滚动数组，这样空间就优化到了 n2n^2。kk 有上限，然后时间优化到了 Θ(n2n)\Theta(n^2 \sqrt{n})。
又有 r−lr-l 也是 n\sqrt{n} 量级的。因为原题中每个回合两人取数的数量之差最多也就为 11，且最多取 n\sqrt{n} 轮，所以 r−lr-l 的量级也是 Θ(n)\Theta(\sqrt{n})。
实际写代码中，kk 和 ∣r−l∣|r-l| 可以从 100100 开始枚举。从 8989 或更低开始枚举可能会 WA，因为 kk 的最大值 kmax⁡k_{\max} 要满足 kmax⁡×(1+kmax⁡)2≥n=4000\frac{k_{\max}\times(1+k_{\max})}{2}\geq n=4000，解得 kmax⁡≥90k_{\max}\geq 90，所以枚举的下界是 9090，但是稍微超一点应该也没啥关系。
这样时间就优化到了 Θ(n2)\Theta(n^2)。
然后也没啥记搜或状态哈希存储的必要。
代码：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...