线性dp——求01串最大连续个数不超过k的方案数，cf1027E 好题！

只写了和dp有关的。。博客 https://www.cnblogs.com/huyufeifei/p/10351068.html

关于状态的继承和转移

这题的状态转移要分开两步来做：

　　1.继承之前状态的合法构造数量

　　2.构造出该状态下特有的新构造数量

这类dp尽量由已知状态推出未知态(加法转移)来做。。。自己用减法转移都不知道边界怎么写。。

#include <cstdio>

#include <algorithm>

const int N = , MO = ;

int f[N][N][], sum[N];

inline void add(int &a, const int &b) {

    a = (a + b) % MO;

    return;

}

int main() {

    int n, k;

    scanf("%d%d", &n, &k);

    for(int j = ; j <= n; j++) {

        f[][j][] = ;

    }

    for(int i = ; i <= n; i++) {

        for(int j = ; j <= n; j++) {

            // f[i][j][0/1]继承前状态

            for(int k = ; k < j && i + k <= n; k++) {

                add(f[i + k][j][], f[i][j][]);

                add(f[i + k][j][], f[i][j][]);

            }

            if(i + j <= n) {//构造出新的方案

                add(f[i + j][j][], f[i][j][]);

                add(f[i + j][j][], f[i][j][]);

            }

        }

    }

    for(int i = ; i <= n; i++)printf("%d ", f[n][i][]);

    long long ans = 0LL;

    for(int i = ; i <= n; i++)

        for(int j = ; (long long)j * i < k && j <= n; j++)

            ans = (ans + f[n][i][] * f[n][j][] % MO) % MO;

    ans = ans *  % MO;

    printf("%lld\n", ans);

}

更新：可以把dp[i][j]转换成前缀和来做，最后相减一下就变成了上面的那种dp[i][j]表示的状态

相比上一中感觉更加直观好写，即对于每种状态，枚举k个连续的1放在末尾，然后把对应的之前的状态加上去就可以了

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = ;

const ll P = 998244353LL;

int n, siz;

ll f[N][N];

inline int min(int x, int y) {

    return x > y ? y : x;

}

int main() {

    scanf("%d%d", &n, &siz);

    f[][] = 1LL;

    for(int i = ; i <= n; i++)

        for(int j = ; j <= i; j++)

            for(int k = ; k <= j; k++)

                f[i][j] = (f[i][j] + f[i - k][min(j, i - k)]) % P;

    for(int i = n; i >= ; i--)

        f[n][i] = (f[n][i] - f[n][i - ] % P + P) % P;

//for(int i = 1; i <= n; i++)printf("%lld ", f[n][i]);

    ll ans = 0LL;

    for(int i = ; i <= n; i++)

        for(int j = ; j * i < siz && j <= n; j++)

            ans = (ans + f[n][i] * f[n][j] % P) % P;

    ans = ans *  % P;

    printf("%lld\n", ans);

}

巴特西

线性dp——求01串最大连续个数不超过k的方案数，cf1027E 好题！

最新文章

热门文章