526互联

Atcoder Grand Contest 046 D - Secret Passage

发布时间 2023-05-08 08:57:43作者: tzc_wk

思路挺自然的一道 agc。

首先发现删除完字符后的状态可以用一个三元组 \((i,j,k)\) 表示，其中 \(i\) 表示删除完之后只剩 \([i+1,n]\) 的后缀，\(j\) 表示可以在后面插入 \(j\) 个 \(0\)，\(k\) 表示可以在后面插入 \(k\) 个 \(1\)，显然不同的三元组能够得到的串是不同的，而一组三元组可以得到的串的个数可以 DP 求解，具体来说，倒着 DP，同时为了防止算重，我们强制要求 \(1\) 的后面只能添加 \(0\)，\(0\) 的后面只能添加 \(1\)，这样转移是 \(O(1)\) 的，具体实现见代码。

接下来考虑哪些三元组 \((i,j,k)\) 可以得到。考虑正着 DP，那么发现每次有两种选择：

  • 从 \(s_{i+1},s_{i+2}\) 中保留一个，删除一个
  • 从保留的字符中拿出一个 \(s_{i+1}\oplus 1\)，插在开头，然后删除这个 \(s_{i+1}\oplus 1\) 同时保留 \(s_{i+1}\)。

转移同样可以 \(O(1)\)，总复杂度 \(O(n^3)\)。

#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
void add(int &x,int v){((x+=v)>=MOD)&&(x-=MOD);}
int n,ok[305][305][305],dp[305][305][305],res;
char s[305];
int main(){
	scanf("%s",s+1);n=strlen(s+1);ok[0][0][0]=1;
	for(int i=1;i<=n;i++)for(int j=n;~j;j--)for(int k=n;~k;k--){
		ok[i][j][k]|=ok[i-1][j][k];
		ok[i][j][k]|=ok[i][j+1][k];
		ok[i][j][k]|=ok[i][j][k+1];
		if(j&&i>=2&&(s[i]=='0'||s[i-1]=='0'))ok[i][j][k]|=ok[i-2][j-1][k];
		if(k&&i>=2&&(s[i]=='1'||s[i-1]=='1'))ok[i][j][k]|=ok[i-2][j][k-1];
		if(j&&s[i]=='0')ok[i][j][k]|=ok[i-1][j-1][k+1];
		if(k&&s[i]=='1')ok[i][j][k]|=ok[i-1][j+1][k-1];
	}
	dp[n][0][0]=1;
	for(int i=n;i;i--)for(int j=0;j<=n;j++)for(int k=0;k<=n;k++){
		add(dp[i-1][j][k],dp[i][j][k]);
		if(s[i]=='0')add(dp[i][j][k+1],dp[i][j][k]);
		if(s[i]=='1')add(dp[i][j+1][k],dp[i][j][k]);
	}
	for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)for(int k=0;k<=n;k++)
		if(ok[i][j][k])add(res,dp[i][j][k]);
	add(res,MOD-1);printf("%d\n",res);
	return 0;
}