2019牛客暑期多校训练营（第一场）

随心情补题，简单的不详细写了。

E  -  ABBA

对于这个题，我没有做出来是因为没看出来，对于一个串来讲，拆成AB和BA时，前n个A一定属于AB，同理B也一样，所以你可以dp这个串的选择方式了，因为构成了无后效性了，后面的选择只和前面A，B的数量有关系，是和顺序没有关系的。考虑添加A的情况：比n少的时候可以直接加A，比n大的时候，只要前面的B比较多，能和多余的A消掉就可以了，这道题不会有点尴尬啊，好多人都过了。

#include<iostream>
#include<cstring>
#include <string>
#include<algorithm>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include <math.h>
#include<vector>
using namespace std;
const int maxn=4e3+10;
const int mod=1e9+7;
typedef long long ll;
ll dp[maxn][maxn];
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=0;i<=n+m;i++)
            for(int j=0;j<=m+n;j++)
                dp[i][j]=0;
        dp[0][0]=1;
        for(int i=0;i<=n+m;i++)
            for(int j=0;j<=m+n;j++)
            {
                if(i<n||(j>i-n))
                    dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
                if(j<m||(i>j-m))
                    dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;
            }
        cout<<dp[n+m][m+n]<<endl;
    }
}