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

链接：https://ac.nowcoder.com/acm/contest/881/E
来源：牛客网

题目描述

The input consists of several test cases and is terminated by end-of-file.
Each test case contains two integers n and m.
* 0≤n,m≤1030≤n,m≤103 * There are at most 2019 test cases, and at most 20 of them has max{n,m}>50max{n,m}>50.

For each test case, print an integer which denotes the result.

1 2
1000 1000
0 0

13
436240410
1

  贪心可得判断结论：：每一个满足条件的字符串都必然满足前n个A与B匹配，后m个A与B匹配的这种分配情况，且不满足这样分配的字符串一定是错的。对于B来说一样。
  这样的话就可以进行dp，dp[i][j]表示现在来说有了i个A和j个B的合法字符串有多少种了。
  转移： 
  假设放A时,需要满足这第i个A是满足之前要求的
 即：如果i+1小于等于n的话随意放即可，因为这样做不需要对已经正确的“前状态”进行判定（对这里不明白的可以私聊我给你解释）  即： if(i+1<=n)  不需要做判定就对了；
  如果i+1大于n的话需要满足有足够的B（代表数量j）可以为多出来的A组成BA（后m个A为了组成BA而存在）
  即：if(i+1>n)  j 需要>= (i+1-n);            
  连立可得：：  能否放下此时的A只需要判断是否j>=(i+1-n)即可。
  B一样

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const int mod = 1e9 + 7;
long long dp[maxn * 4][maxn * 2];
int n, m;
int main() {
    ios::sync_with_stdio(0);
    while (cin >> n >> m) {
        for (int i = 0; i <= n + m; i++)
            for (int j = 0; j <= n + m; j++)dp[i][j] = 0;
        dp[0][0] = 1;
        for (int i = 0; i <= n + m; i++) {
            for (int j = 0; j <= n + m; j++) {
                if (j >= i + 1 - n) {
                    dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod;
                }
                if (i >= j + 1 - m) {
                    dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % mod;
                }
            }
        }
        cout << dp[n + m][n + m] << "\n";
    }
    return 0;
}