ABBA

Posted on | In , , ,

题目链接

题意

一个长度为$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
#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;
}
0%