题意
一个长度为$2(n+m)$字符串只由$’A’,’B’$构成，且可以将它分成$n+m$个子序列，其中$n$个为$AB$，$m$个为$BA$。问这样的字符串有多少个。
思路
dp
$dp[i][j]$表示到第$i$个字符，选了$j$个$A$，我们判断一下是否合法状态，转移就行了。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
using namespace std;
typedef long long ll;
const int N = 2e3 + 5;
const ll mod = 1e9 + 7;
ll dp[N * 2][N];
bool (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("%lldn", 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;
}
|
近期评论