2024ICPC成都——B.Athlete Welcome Ceremony

题目链接

题目大意:
$a,b,c$是每个人的衣服,相邻的人的衣服不可以相同,给定字符串,第$i$个位置代表第$i$个人的衣服,如果是问号则是待分配，$q$次询问,每次给定三个数x,y,z表示分别制作了x件a,y件b,z件c,问分配方案数

分析
是一道$dp$+三维前缀和的题,题目的n很小只有300，这就引导我们往$dp$上去想,考虑$dp$的设计
$f[i][j][k][l]$:前i个位置,分配了j个a,k个b,第i个位置是’a’+l的方案数
如果$i$这一位是?,那么显然a,b,c都是可以尝试分配的,这样设计f转移式比较好写，直接看代码即可

计算高维前缀和,我们要记录$cnt$数组用来存第i位以前的$?$数量,一开始,只要刚好把问号数量分配完的方案才会有值,先把这个处理完就可以开始前缀和计算了

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;

constexpr int mod = 1e9+7;
int n,q,f[305][305][305][3],cnt[323];
int sum[305][305][305];
string s;
//f[i][j][k][l] 前i个数用了j个a,用了k个b,第i位是l+'a'的方案数
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>q;
    cin>>s;
    s = " "+s;
    for(int i = 1;i<=n;++i) cnt[i] = cnt[i-1]+(s[i]=='?');
    if(s[1]=='?') f[1][1][0][0] = f[1][0][1][1] = f[1][0][0][2] = 1;
    else f[1][0][0][s[1]-'a']=1;

    for(int i = 2;i<=n;++i){
        for(int j = 0;j<=cnt[i];++j){
            for(int k = 0;k<=cnt[i];++k){
                if(s[i]!='?'){
                    f[i][j][k][s[i]-'a'] = (f[i][j][k][s[i]-'a']+f[i-1][j][k][0])%mod;//上一层方案数
                    f[i][j][k][s[i]-'a'] = (f[i][j][k][s[i]-'a']+f[i-1][j][k][1])%mod;//上一层方案数
                    f[i][j][k][s[i]-'a'] = (f[i][j][k][s[i]-'a']+f[i-1][j][k][2])%mod;//上一层方案数
                    f[i][j][k][s[i]-'a'] = (f[i][j][k][s[i]-'a']-f[i-1][j][k][s[i]-'a']+mod)%mod;//因为不能相邻减去不符合条件的
                }else{
                    if(j){
                        f[i][j][k][0] = (f[i-1][j-1][k][1]+f[i][j][k][0])%mod;
                        f[i][j][k][0] = (f[i-1][j-1][k][2]+f[i][j][k][0])%mod;
                    }
                    if(k){
                        f[i][j][k][1] = (f[i-1][j][k-1][0]+f[i][j][k][1])%mod;
                        f[i][j][k][1] = (f[i-1][j][k-1][2]+f[i][j][k][1])%mod;
                    }
                    if(cnt[i]-j-k){
                        f[i][j][k][2] = (f[i-1][j][k][0]+f[i][j][k][2])%mod;
                        f[i][j][k][2] = (f[i-1][j][k][1]+f[i][j][k][2])%mod;
                    }
                }
            }
        }
    }

    //处理有值的i个a,j个b,cnt[n]-i-j个c的方案
    for(int i = 0;i<=cnt[n];++i){
        for(int j = 0;i+j<=cnt[n];++j){
            sum[i][j][cnt[n]-i-j] = (f[n][i][j][0]+sum[i][j][cnt[n]-i-j])%mod;
            sum[i][j][cnt[n]-i-j] = (f[n][i][j][1]+sum[i][j][cnt[n]-i-j])%mod;
            sum[i][j][cnt[n]-i-j] = (f[n][i][j][2]+sum[i][j][cnt[n]-i-j])%mod;
        }
    }

    //三维前缀和
    for(int i = 0;i<=300;++i){
        for(int j = 0;j<=300;++j){
            for(int k = 0;k<=300;++k){
                if(i>0) sum[i][j][k] = (sum[i-1][j][k]+sum[i][j][k])%mod;
                if(j>0) sum[i][j][k] = (sum[i][j-1][k]+sum[i][j][k])%mod;
                if(k>0) sum[i][j][k] = (sum[i][j][k-1]+sum[i][j][k])%mod;
                if(i>0&&j>0) sum[i][j][k] = (sum[i][j][k]-sum[i-1][j-1][k]+mod)%mod;
                if(i>0&&k>0) sum[i][j][k] = (sum[i][j][k]-sum[i-1][j][k-1]+mod)%mod;
                if(k>0&&j>0) sum[i][j][k] = (sum[i][j][k]-sum[i][j-1][k-1]+mod)%mod;
                if(i>0&&j>0&&k>0)sum[i][j][k] = (sum[i][j][k]+sum[i-1][j-1][k-1])%mod;
            }
        }
    }
    while(q--){
        int x,y,z;
        cin>>x>>y>>z;
        cout<<sum[x][y][z]<<"\n";
    }
    return 0;
}

原文地址：https://blog.csdn.net/theskyinblue/article/details/143895330

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！