题解：AT_yahoo_procon2019_qual_f Pass

· · 题解

Solution-Pass

题目传送门

题目分析

在读入字符串时，先预处理出每个人具有的红色与蓝色的气球数，分别记为 red_{i} 和 blue_{i}，用 f_{i,j} 表示用 i 个红球和 j 个蓝球能组成的队伍方案数。

由于 |S| \le 2000，考虑时间复杂度 O(n^{2}) 的状态转移方程。

初始化 f_{0,0}=1，当 i + j < n 时，若 i > red_{i + j} 或 j > blue_{i + j}，方案不合法，我们就可以列出状态转移方程：

f_{i,j} \gets f_{i-1,j} + f_{i,j}(i > 0),f_{i,j} \gets f_{i,j - 1} + f_{i,j}(j > 0)

AC 代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e3 + 5 ;
const int Mod = 998244353 ;
int n , f[N][N] , b[N] , r[N] ;
string s ; 
inline int read(){
    int x = 0 , f = 1 ;
    char ch = getchar() ;
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1 ;
        ch = getchar() ;
    }
    while('0' <= ch && ch <= '9'){
        x = (x << 1) + (x << 3) + (ch ^ 48) ; 
        ch = getchar(); 
    }
    return x * f ;
}
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> s ;
    n = s.size() ;
    s = ' ' + s ;//字符串下标从1开始
    for(int i = 1;i <= n;i ++){
        b[i] = b[i - 1] + (s[i] - '0');
        r[i] = r[i - 1] + 2 - (s[i] - '0') ;//预处理
    }
    f[0][0] = 1;
    for(int i = 0;i <= b[n];i ++){
        for(int j = 0;j <= r[n];j ++){
            if(! i && ! j) continue ;
            int cnt = i + j;
            if((i > b[cnt] || j > r[cnt]) && cnt < n) f[i][j] = 0;
            else{
                if( i ) f[i][j] += f[i - 1][j] ;
                if( j ) f[i][j] += f[i][j - 1] ;
            }//状态转移
            f[i][j] %= Mod ;
        }
    }
    cout << f[b[n]][r[n]] ;
    return 0;
}