题解：AT_yahoo_procon2019_qual_f Pass

jinglinbankemeng · 2024-06-20 16:06:32 · 题解

前言：

竟然有如此水的蓝题。

思路：

这是一道非常经典的DP问题。

用 dp[i][j] 来表示前 i+j 次操作中共收到 i 个红球和 j 个蓝球的方案。

若此状态满足每个数恰好在数列中出现了 2 次且第 i 位上的数都必须小于等于 i。

则 dp[i][j] \gets dp[i-1][j]+dp[i][j-1]。

否则 dp[i][j] \gets 0。

AC Code：

#include <bits/stdc++.h>
using namespace std;
const long long N=4010;
long long n,l[N],r[N],dp[N][N],mod=998244353;
string s;
int main()
{
    //  freopen(".in","r",stdin);
    //  freopen(".out","w",stdout);
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> s;
    n=s.size();
    for(long long i=1;i<=n;i++)
    {
        l[i]=l[i-1];
        r[i]=r[i-1];
        if(s[i-1]=='0')
        {
            l[i]+=2;
        }
        else if(s[i-1]=='1')
        {
            l[i]++;
            r[i]++;
        }
        else
        {
            r[i]+=2;
        }
    }
    dp[0][0]=1;
    for(long long i=0;i<=l[n];i++)
    {
        for(long long j=0;j<=r[n];j++)
        {
            if(i+j==0)
            {
                continue;
            }
            long long k=i+j;
            if((j>r[k]||i>l[k]) && k<n)
            {
                dp[i][j]=0;
            }
            else{
                if(i)
                {
                    dp[i][j]+=dp[i-1][j];
                }
                if(j)
                {
                    dp[i][j]+=dp[i][j-1];
                }
                if(dp[i][j]>=mod)
                {
                    dp[i][j]-=mod;
                }
            }
        }
    }
    cout << dp[l[n]][r[n]] << endl;
    return 0 ;
}