#C241002C. 简单博弈

标签（Label）

动态规划
状态压缩

网址（Website）

题目详情 - 简单博弈 - Super

题解 - 简单博弈 - Super

题解（Solution）

出题者题解

### 算法分析

输的代价过大，但对于每一个序列都可以保证不失败。

记 $f[i][s_1][s_2][s_3]$ 代表和第 $i$ 个对手游戏时出 $0/1/2$ 后得到的最大分数为 $s_1, s_2, s_3$ 时的方案数。

若第 $i$ 个对手可以出 $0$，则 $f[i][\max(s_2, s_3)][\max(s_1, s_3)+1][-\infty] \leftarrow f[i-1][s_1][s_2][s_3]$ 第 $i$ 个对手可以出 $1/2$ 时同理转移，最终答案为 $\sum \max(s_1, s_2, s_3) \times f[n][s_1][s_2][s_3]$ 。

时间复杂度 $O(n^4)$。

发现一定有一维是 $-\infty$，考虑优化掉这一维，记 $f[i][s_1][s_2][k]$ 代表和第 $i$ 个对手游戏时出 $(k+1)%3, (k+2)%3$ 时（即本次平局或赢），本场的最大得分为 $s_1, s_2$ 的方案数。

答案为 $\sum \max(s_1, s_2) \times f[n][s_1][s_2][k]$

若第 $i$ 个对手可以出 $0$，则 $k=2$，因为出 $2$ 必输。

考虑前一次出的手势：

若前一次对手出的 $0$，则前一次 $k=2$，自己出手为 $0$ 时最大得分为 $s_1$，出手为 $1$ 时最大得分为 $s_2$，本次出手为 $0$ 时得分为 $s_2$，出手为 $1$ 时得分为 $s_1+1$，即

$f[i][s_2][s_1+1][2] \leftarrow f[i-1][s_1][s_2][2]$

若前一次对手出的 $1$，则前一次 $k=0$，自己出手为 $1$ 时最大得分为 $s_1$，出手为 $2$ 时最大得分为 $s_2$，本次出手为 $0$ 时得分为 $\max(s_1, s_2)$，出手为 $1$ 时得分为 $s_2+1$，即

$f[i][\max(s_1, s_2)][s_2+1][2] \leftarrow f[i-1][s_1][s_2][0]$

若前一次对手出的 $2$，则前一次 $k=1$，自己出手为 $2$ 时最大得分为 $s_1$，出手为 $0$ 时最大得分为 $s_2$，本次出手为 $0$ 时得分为 $s_1$，出手为 $1$ 时得分为 $\max(s_1, s_2)+1$，即

$f[i][s_1][\max(s_1, s_2)+1][2] \leftarrow f[i-1][s_1][s_2][1]$

在第 $i$ 个对手可以出 $1/2$ 时同理转移。

时间复杂度 $O(n^3)$。

考虑式 $\sum \max(s_1, s_2) \times f[n][s_1][s_2][k]$，又 $f[n][s_1][s_2][k]$ 可以由若干个 $f[n-1][s_1’][s_2’][k’]$ 转移而来，那么上式化为

$\sum \max(s_1, s_2) \times \sum f[n-1][s_1’][s_2’][k’] \\= \sum (\max(s_1’, s_2’) + \Delta(s_1’, s_2’)) \times f[n-1][s_1’][s_2’][k’] \\= \sum \max(s_1’, s_2’) \times f[n-1][s_1’][s_2’][k’] + \sum \Delta(s_1’, s_2’) \times f[n-1][s_1’][s_2’][k’]$

其中 $\Delta(s_1’, s_2’) = \max(s_1, s_2) - \max(s_1’, s_2’)$。

初始 $\max(0, 0) \times f[0][0][0][k] = 0$，那么只需要每次统计 $f[n-1][s_1’][s_2’][k’]$ 向 $f[n][s_1][s_2][k]$ 转移时对应的增量，相加就是答案。

考虑上面 $k=2$ 对应的三种情况：

$\Delta(s_1’, s_2’) = \max(s_1+1, s_2) - \max(s_1, s_2) = [s_1 - s_2 \geq 0]$
$\Delta(s_1’, s_2’) = \max(\max(s_1, s_2), s_2+1) - \max(s_1, s_2) = [s_1 - s_2 \leq 0]$
$\Delta(s_1’, s_2’) = \max(\max(s_1, s_2)+1, s_1) - \max(s_1, s_2) = 1$

增量只与 $s_1 - s_2$ 的值有关，那么我们观察 $s_1 - s_2 = t$ 的变化：

$s_1 - s_2 \rightarrow s_2 - s_1 + 1$，即 $t \rightarrow -t + 1$
$s_1 - s_2 \rightarrow \max(s_1, s_2) - (s_2+1)$，即 $t \leq 0$ 时为 $-1$，其余情况为 $t-1$
$s_1 - s_2 \rightarrow s_1 - \max(s_1, s_2) - 1$，即 $t \geq 0$ 时为 $-1$，其余情况为 $t-1$

于是可以仅维护 $s_1 - s_2 = t$ 的值，并在转移的同时统计答案。

$f[i][-t+1][2] \leftarrow f[i-1][t][2], ans \leftarrow \Delta \times f[i-1][t][2]$
$f[i][\max(0, t)-1] \leftarrow f[i-1][t][0], ans \leftarrow \Delta \times f[i-1][t][0]$
$f[i][\min(0, t)-1] \leftarrow f[i-1][t][1], ans \leftarrow \Delta \times f[i-1][t][1]$

实际写代码时可以枚举对手 $i$ 和 $i-1$ 的出手差值来转移，时间复杂度 $O(n^2)$。

代码（Code）

$n^4$ 代码

详情如下

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int N = 301234;
bool ST;

int n,ans,a[N];

inline void add(int &x,int y){
	if((x+=y)>=mod) x-=mod;
}//0-?? 1-? 2-?? 

int f[2][305][305][305]; 
inline void solve(){
	n = rd();For(i,1,n) a[i] = rd();
	
	f[0][0][0][0] = 1;
	For(i,1,n){
		int p = i&1, b = (i-1)&1;
		memset(f[p],0,sizeof f[p]);
		For(s1,0,i){
			For(s2,0,i){
				For(s3,0,i){
					if(a[i]==0 || a[i]==-1)  f[p][max(s2,s3)][max(s1,s3)+1][0] += f[b][s1][s2][s3];
					if(a[i]==1 || a[i]==-1)  f[p][0][max(s1,s3)][max(s1,s2)+1] += f[b][s1][s2][s3];
					if(a[i]==2 || a[i]==-1)  f[p][max(s2,s3)+1][0][max(s1,s2)] += f[b][s1][s2][s3];
				}
			}
		}
	}
	For(s1,0,n+1) For(s2,0,n+1) For(s3,0,n+1) add(ans, f[n&1][s1][s2][s3]*max({s1,s2,s3}));
	cout<<ans<<'\n';
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	int T = 1, Tim = clock();
	while(T--) solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}

$n^3$ 代码

详情如下

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int N = 301234;
bool ST;

int n,ans,a[N];

inline void add(int &x,int y){if((x+=y)>=mod) x-=mod;}
inline int trs(int x){return x%3;}

int f[305][305][305][5];
inline void solve(){
	n = rd();For(i,1,n) a[i] = rd();
	
	if(a[1]==0 || a[1]==-1) f[1][0][1][2]=1;
	if(a[1]==1 || a[1]==-1) f[1][0][1][0]=1;
	if(a[1]==2 || a[1]==-1) f[1][0][1][1]=1;
	For(i,2,n){
		int p = i, b = (i-1);
		For(s1,0,i-1){
			For(s2,0,i-1){
				if(a[i]==0 || a[i]==-1){
					add(f[p][max(s1,s2)][s2+1][2], f[b][s1][s2][0]);
					add(f[p][s1][max(s1,s2)+1][2], f[b][s1][s2][1]);
					add(f[p][s2][s1+1][2], f[b][s1][s2][2]);
				}
				if(a[i]==1 || a[i]==-1){
					add(f[p][s2][s1+1][0], f[b][s1][s2][0]);
					add(f[p][max(s1,s2)][s2+1][0], f[b][s1][s2][1]);
					add(f[p][s1][max(s1,s2)+1][0], f[b][s1][s2][2]);					
				}
				if(a[i]==2 || a[i]==-1){
					add(f[p][s1][max(s1,s2)+1][1], f[b][s1][s2][0]);
					add(f[p][s2][s1+1][1], f[b][s1][s2][1]);
					add(f[p][max(s1,s2)][s2+1][1], f[b][s1][s2][2]);					
				}
			}
		}
	}
	For(s1,0,n) For(s2,0,n) For(k,0,2) 
		add(ans, f[n][s1][s2][k]*max(s1,s2)%mod);
	cout<<ans<<'\n';
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	int T = 1, Tim = clock();
	while(T--) solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}