[ZJOI]2008 生日聚会

显然DP。

将题目转化下：求由n个0、m个1组成，且满足任意子串0的数量和1的数量差绝对值不超过k的01串数量。n, m≤150，k≤20。

直接做没什么思路，，那我们尽量利用题目的时间和空间限制，以达到清晰、方便的方程转移。

由于题目n、m很小，可以考虑O(nm)带k的几次方的算法。

设f[a][b][l][h]表示当前序列中放了a个1，b个0，所有后缀中，男生减女生的差最大为l，女生减男生的差最大为h的方案数。

那么状态转移显然-> f[a][b][l][h] 可以向 f[a+1][b][l+1][max(h-1),0] 或 f[a][b+1][max(l-1)][h+1] 转移；最后答案统计f[n][m][l][h]（枚举l,h）。

Code:

#include<bits/stdc++.h>
using namespace std;

;
;

][];

int main(){
    int n,m,k;
    cin>>n>>m>>k;
    f[][][][] = ;
    ;a<=n;++a)
    ;b<=m;++b)
    ;l<=k;++l)
    ;h<=k;++h)
    if(f[a][b][l][h]){
        int cnt = f[a][b][l][h];
        f[a+][b][l+][max(h-,)] += cnt;f[a+][b][l+][max(h-,)]%=mod;
        f[a][b+][max(l-,)][h+] += cnt;f[a][b+][max(l-,)][h+]%=mod;
    }
    ;
    ;i<=k;++i)
        ;j<=k;++j)
        ans = (ans + f[n][m][i][j])%mod;
    cout<<ans<<endl;
}

巴特西

[ZJOI]2008 生日聚会

最新文章

热门文章