2019牛客暑期多校训练营（第一场）E-ABBA
登录—专业IT笔试面试备考平台_牛客网
https://ac.nowcoder.com/acm/contest/881/E
链接：https://ac.nowcoder.com/acm/contest/881/E
来源：牛客网
题目描述
Bobo has a string of length 2(n + m) which consists of characters `A` and `B`. The string also has a fascinating property: it can be decomposed into (n + m) subsequences of length 2, and among the (n + m) subsequences n of them are `AB` while other m of them are `BA`.
Given n and m, find the number of possible strings modulo (109+7)(109+7).
Given n and m, find the number of possible strings modulo (109+7)(109+7).
输入描述:
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.
求解满足可以拆成n个“AB”的子序列和m个“BA”子序列的字符串数量有几个？
贪心可得判断结论：：每一个满足条件的字符串都必然满足前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;
}
