题解：AT_yahoo_procon2019_qual_f Pass

· · 题解

好水的蓝

思路

读入后先预处理出到每个人时具有的红蓝气球数 red_i 和 blue_i，设 f_{i,j} 为用 i 个红球和 j 个蓝球所能组成队伍的方案数，显然状态转移方程为：

f_{i,j}+=f_{i-1,j}(i\ne 0) f_{i,j}+=f_{i,j-1}(j\ne 0)

边界处理

首先有 f_{0,0}=1。

同时，当 i+j<n 时，若 i>red_{i+j} 或 j>blue_{i+j}，那么此时方案不合法，应有 f_{i,j}=0。

Code：

短码来喽~

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Ratio=0;
const int N=4005;
const int mod=998244353;
string s;
int n,red[N],blue[N],f[N][N];
namespace Wisadel
{
    short main()
    {
        cin>>s;n=s.size();f[0][0]=1;
        for(int i=1;i<=n;i++)
            red[i]=red[i-1]+2-(s[i-1]-'0'),
            blue[i]=blue[i-1]+(s[i-1]-'0');
        for(int i=0;i<=red[n];i++)
            for(int j=0;j<=blue[n];j++)
            {
                if(!i&&!j) continue;
                int k=i+j;
                if((i>red[k]||j>blue[k])&&k<n) f[i][j]=0;
                else f[i][j]+=(i?f[i-1][j]:0)+(j?f[i][j-1]:0);
                f[i][j]%=mod;
            }
        printf("%d\n",f[red[n]][blue[n]]);
        return Ratio;
    }
}
int main(){return Wisadel::main();}

完结撒花~