题意：
给定一个只包含012序列，0表示这个人有2个红球，1表示一个红球一个蓝球，2表示两个蓝球。进行n*2次游戏，每次游戏所有有球的人选择一个球递给前一个人，第一个人把球放到一个序列中，‘r‘表示红球，‘b‘表示蓝球，问一共多少种序列。
分析：
一定要满足前i个人的所有红球>=序列前i个位置的红球，蓝球同理，然后dp。
f[i][j]表示到第i个位置，有j个红球的方案数。
代码：
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<cctype> #include<set> #include<queue> #include<vector> #include<map> using namespace std; typedef long long LL; inline int read() { int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch==‘-‘)f=-1; for(;isdigit(ch);ch=getchar())x=x*10+ch-‘0‘;return x*f; } const int N = 4005, mod = 998244353; int sum[N][2], f[N][N]; char s[N]; inline void add(int &x,int y) { x += y; x = x >= mod ? x - mod : x; } int main() { scanf("%s", s + 1); int n = strlen(s + 1); for (int 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] >= 1) f[1][1] = 1; if (sum[1][1] >= 1) f[1][0] = 1; for (int i = 2; i <= (n << 1); ++i) { for (int j = 0; j <= i; ++j) { int r = j, b = i - j; if (r > sum[min(i, n)][0] || b > sum[min(i, n)][1]) continue;; add(f[i][j], f[i - 1][j]); if (j) add(f[i][j], f[i - 1][j - 1]); } } cout << f[n + n][sum[n][0]]; return 0; }
Yahoo Programming Contest 2019 F - Pass
原文：https://www.cnblogs.com/mjtcn/p/10373731.html