ABAB--2019牛客暑期多校训练营(第一场)- E题

题目大意：

构造一个长为 的字符串，使得能从中按顺序挑出 个"AB"子串和 个"BA"子串，问这样的字符串一共有多少个。

一个似乎比较明显的dp问题，类似于括号配对。

二维dp,dp[i][j],表示前i个字符,字母A和字母B的差为j个，然后就可以进行dp了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=1000000+10;
const ll mod=1000000007;
const int INF=0x3f3f3f3f;
ll dp[1000*4+10][1000*4];
int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m)){
        for(int i=1;i<=(n+m)*2;i++){
            for(int j=1000-m-1;j<=1000+n+1;j++){
                dp[i][j]=0;
            }
        }
        dp[0][1000]=1;
        for(int i=1;i<=(n+m)*2;i++){
            for(int j=1000-m;j<=1000+n;j++){
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
                dp[i][j]%=mod;
            }
        }
        printf("%lld\n",dp[(n+m)*2][1000]%mod);
    }
    return 0;
}