傳送門

題目大意

給定一個(gè)只包含012序列，0表示這個(gè)人有2個(gè)紅球，1表示一個(gè)紅球一個(gè)藍(lán)球，2表示兩個(gè)藍(lán)球。進(jìn)行n*2次游戲，每次游戲所有有球的人選擇一個(gè)球遞給前一個(gè)人，第一個(gè)人把球放到一個(gè)序列中，'r'表示紅球，'b'表示藍(lán)球，問一共多少種序列

分析

一定要滿足前i個(gè)人的所有紅球>=序列前i個(gè)位置的紅球，藍(lán)球同理，然后dp

f[i][j]表示到第i個(gè)位置，有j個(gè)紅球的方案數(shù)

代碼

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cctype> #include<cmath> #include<cstdlib> #include<ctime> #include<queue> #include<vector> #include<set> #include<map> #include<stack> using namespace std; const int mod = 998244353; char s[100100]; int n,m,dp[4010][4010],sum[2010][2]; int main(){int i,j,k;scanf("%s",s+1);n=strlen(s+1);for(i=1;i<=n;i++){if(s[i]=='0')sum[i][0]+=2;else if(s[i]=='1')sum[i][0]++,sum[i][1]++;else sum[i][1]+=2;sum[i][0]+=sum[i-1][0],sum[i][1]+=sum[i-1][1];}if(sum[1][0])dp[1][0]=1;if(sum[1][1])dp[1][1]=1;for(i=2;i<=2*n;i++)for(j=0;j<=i;j++){if(j>sum[min(i,n)][1]||i-j>sum[min(i,n)][0])continue;dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;if(j)dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod;}cout<<dp[2*n][sum[n][1]];return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/yzxverygood/p/10527407.html

總結(jié)

以上是生活随笔為你收集整理的Yahoo Programming Contest 2019 F - Pass的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。