BD202404 110串

百度之星一场，t4

题目链接：

对于这种连续状态限制的字符串方案数，首先考虑dp，

首先定义好每个状态方便转移，0状态是结尾为0，1状态是结尾1个连续1，2状态是结尾两个连续1，有以下关系

if(s[i] == '1') {
    if(j > 0) dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1]) % mod;
    dp[i][j][1] = (dp[i][j][1] + dp[i - 1][j][0]) % mod;
    dp[i][j][2] = (dp[i][j][2] + dp[i - 1][j][1] + dp[i - 1][j][2]) % mod;
} else {
    dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][0] + dp[i - 1][j][1]) % mod;
    if(j > 0) dp[i][j][1] = (dp[i][j][1] + dp[i - 1][j - 1][0]) % mod;
    if(j > 0) dp[i][j][2] = (dp[i][j][2] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2]) % mod;
}

可以发现每个分类讨论的转移个数不加本身是有5条(转移图可知有6条，有一条不合法)，这是基于转移的路径确定，主要s[i]区别就是转移的代价变化

• 本题卡了内存，故要优化成滚动数组方式转移

#include<bits/stdc++.h>
#define int long long
using namespace std;
using ull = unsigned long long;
using ll = long long;
using PII = pair<int,int>;
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define lowbit(x) (x) & (-x)
#define endl "\n" 
#define pb push_back
const int N=5e3+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
ll dp[2][N][3];
void solve()
{
    int n, k; cin >> n >> k;
    string s; cin >> s; s = " "  + s;
    dp[0][0][0] = 1;
    for(int i = 1; i <= n; i ++) {
        int u = i & 1;
        for(int j = 0; j <= k; j ++) {
            if(s[i] == '1') {
                if(j > 0) dp[u][j][0] = (dp[u][j][0] + dp[u ^ 1][j - 1][0] + dp[u ^ 1][j - 1][1]) % mod;
                dp[u][j][1] = (dp[u][j][1] + dp[u ^ 1][j][0]) % mod;
                dp[u][j][2] = (dp[u][j][2] + dp[u ^ 1][j][1] + dp[u ^ 1][j][2]) % mod;
            } else {
                dp[u][j][0] = (dp[u][j][0] + dp[u ^ 1][j][0] + dp[u ^ 1][j][1]) % mod;
                if(j > 0) dp[u][j][1] = (dp[u][j][1] + dp[u ^ 1][j - 1][0]) % mod;
                if(j > 0) dp[u][j][2] = (dp[u][j][2] + dp[u ^ 1][j - 1][1] + dp[u ^ 1][j - 1][2]) % mod;
            }
        }
        memset(dp[u ^ 1], 0, sizeof dp[u ^ 1]);
    }
    ll res = 0;
    int u = n & 1;
    for(int j = 0; j <= k; j ++) {
        res = (res + dp[u][j][0] + dp[u][j][1] + dp[u][j][2]) % mod;
    }
    cout << res << endl;
}
signed main()
{
    int T = 1;
    //cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}