ABBA
登录—专业IT笔试面试备考平台_牛客网
https://ac.nowcoder.com/acm/contest/881/E
题意
一个长度为2(n+m)字符串只由'A','B'构成，且可以将它分成n+m个子序列，其中n个为AB，m个为BA。问这样的字符串有多少个。
思路
dp
一个长度为2(n+m)字符串只由'A','B'构成，且可以将它分成n+m个子序列，其中n个为AB，m个为BA。问这样的字符串有多少个。
思路
dp
dp[i][j]表示到第i个字符，选了j个A，我们判断一下是否合法状态，转移就行了。
到位置i选了j个A，那么也就是说选了i-j个B，我们知道了A和B分别的个数。
下次再选A，或者再选B，转移到dp[i+1][j]或dp[i+1][j+1]，我们判断这样的状态是否合法，即j的大小不会超过B数量，A与B之差与j、i-j的差的关系。
通过考虑这些因素，将其封装成check
具体见代码。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3 + 5;
const ll mod = 1e9 + 7;
ll dp[N * 2][N];
bool check(int i, int j, int n, int m)
{ return j >= 0 && j <= i && j - (i - j) <= n && (i - j) - j <= m;
}
int main()
{ int n, m; while (scanf("%d%d", &n, &m) == 2) { dp[0][0] = 1; for (int i = 1; i <= 2 * (n + m); i++) { for (int j = 0; j <= n + m; j++) { if (check(i - 1, j - 1, n, m)) dp[i][j] = (dp[i - 1][j - 1] + dp[i][j]) % mod; if (check(i - 1, j, n, m)) dp[i][j] = (dp[i - 1][j] + dp[i][j]) % mod; } } printf("%lld\n", dp[2 * (n + m)][n + m]); for (int i = 1; i <= 2 * (n + m); i++) for (int j = 0; j <= n + m; j++) dp[i][j] = 0; } return 0;
} 清空数组不要memset，有可能会T的。
投递科大讯飞等公司8个岗位 >
京东HR面42人在聊