2019暑假 牛客第一场E题

//知识点:dp

dp[a][b]表示前a+b个中有a个A,b个B那么我们要找的结果就是dp[n+m][n+m]

先找边界条件

注意最后要配成n个AB和m个BA,那么就说明不能有n个以上的A或者m个以上的B在前

以第一个样例为例 1个AB,2个BA,有三个A和三个B

当出现两个A在前: AA____  或者三个B在前: BBB___ 这时的情况不满足dp[a][b]=0;

总结一下就是前面有n个单独的A或者m个单独的B

单独的表示没有被使用(被搭配)

dp[a][b]=dp[a-1][b]+dp[a][b-1]

注意这个加法要取余数

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int maxn=1e3+5;
long long dp[maxn+maxn][maxn+maxn];
long long Plus(long long a,long long b)//相加取余数
{
    return (a+b>mod?a+b-mod:a+b);
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        for(int b=0;b<=m;b++)//m个b以下都成立
        {
            dp[0][b]=1;
        }
        for(int b=m+1;b<=n+m;b++)//超过m个都不成立
        {
            dp[0][b]=0;
        }
        for(int a=1;a<=n;a++)//对A讨论,先分配n个AB中的A
        {
            dp[a][0]=1;//n个A以下都成立
            for(int b=1;b<=m+a;b++)//有a个和A进行搭配,m个作为BA的开头
            {
                dp[a][b]=Plus(dp[a][b-1],dp[a-1][b]);
            }
            for(int b=m+a+1;b<=m+n;b++)//搭配完后单独的B超过m个不成立
            {
                dp[a][b]=0;
            }
        }
        for(int a=n+1;a<=n+m;a++)//n个AB中开头的A分配完

        {
            for(int b=0;b<a-n;b++)//a-n是超过n的A的个数,要相应的B搭配,不然单独的A超过n个
            {
                dp[a][b]=0;
            }
            for(int b=a-n;b<=m+n;b++)
            {
                dp[a][b]=Plus(dp[a-1][b],dp[a][b-1]);
            }
        }
        cout<<dp[n+m][n+m]<<endl;
    }
}