2024百度之星第一场-110串

补题链接： 码蹄集

三个状态转移的计数dp

先确定状态

n个数至多修改k次，保证不出现字串“110”

常规想法先把状态确定为dp[n][k][0/1]，前n个数，修改k次后，末尾数为0/1，不能转移再换思路。

初始状态设定如下：

dp[1][(s[1]=='0')?0:1][0]=1;
dp[1][(s[1]=='1')?0:1][1]=1;

即，第一个数的所有状态处理，比如s[1]==‘1’,那么状态就是dp[1][0][1]=1,dp[1][1][0]=0。

考虑状态转移 

我们需要避免出现110，考虑第i位，第i-1位，第i-2位之间的关系。

首先很自然的想法，如果第i位是1，那么无论前面两位取什么，结果都是满足的，全部加起来，即：dp[i][j][1]=dp[i][j或j-1][1]+dp[i][j或j-1][0];

这个修改数量取j还是j-1取决于假定末尾和实际末尾是否一致，所以我们可以这么写

int p1_1=(s[i]=='1'?0:1);
dp[i][j][1]=dp[i-1][j-p1_1][1]+dp[i-1][j-p1_1][0];

 这种情况就是XX1，即最后一位取1，前面两位取0或1都行。

同样的情况有下面三种：

XX1

X00

010

我们解决完了XX1，后面两种思路也是一样的，代码如下：

int p1_0=(s[i]=='0'?0:1);
int p1_1=(s[i]=='1'?0:1);
int p2_1=(s[i-1]=='1'?0:1);
dp[i][j][1]=dp[i-1][j-p1_1][1]+dp[i-1][j-p1_1][0];
dp[i][j][0]+=dp[i-1][j-p1_0][0]+dp[i-2][j-p1_0-p2_1][0];

其实就是当第i位为0时，之能从第i-1位为0和第i-2位为0转移过来。

状态转移就完成了，考虑三个细节：范围，取模以及滚动，最终代码如下。

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
char s[N];
int dp[3][N][2];//以0/1结尾 
const int mod=998244353;
int f(int x){
    return (x+3)%3;
}
void work(){
	int n,k;cin>>n>>k;
	for (int i=1;i<=n;i++){
		cin>>s[i];
	}
	dp[f(1)][(s[1]=='0')?0:1][0]=1;
	dp[f(1)][(s[1]=='1')?0:1][1]=1;
	for (int i=2;i<=n;i++){
		for (int j=0;j<=k;j++){
			int p1_0=(s[i]=='0'?0:1);
			int p1_1=(s[i]=='1'?0:1);
			int p2_1=(s[i-1]=='1'?0:1);
			dp[f(i)][j][0]=dp[f(i)][j][1]=0;
			if (i>=2&&j-p1_1>=0) dp[f(i)][j][1]=(dp[f(i-1)][j-p1_1][1]+dp[f(i-1)][j-p1_1][0])%mod;
			if (i>=2&&j-p1_0>=0) (dp[f(i)][j][0]+=dp[f(i-1)][j-p1_0][0])%=mod;
			if (i>=3&&j-p1_0-p2_1>=0) (dp[f(i)][j][0]+=dp[f(i-2)][j-p1_0-p2_1][0])%=mod;
			if (i<3&&j-p1_0>=0) (dp[f(i)][j][0]+=dp[f(i-1)][j-p1_0][1])%=mod;
		}
	}
	int ans=0;
	for (int j=0;j<=k;j++) (ans+=(dp[f(n)][j][0]+dp[f(n)][j][1])%mod)%=mod;
	cout<<ans<<"\n";
}
signed main(){
	work();
	return 0;
}

完结撒花