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

题意：

问你长度为2 * （n+m）的字符串由（n+m）个A和B组成，要求有n个AB子序列和m个BA子序列，这样的串有几个?

题目链接：

https://ac.nowcoder.com/acm/contest/881/E

题解：

f[now][index]  代表 当前状态下  前index个字符的方案数多少   

假设有j个A  那么就有 （i - j）个B   （i为当前位置， 可以看下面AC代码）

对于A, 优先变为AB, 故num(AB) = num(A) - num(B) = 2 * j - i

对于B, 优先变为BA, 故num(BA) = num(B) - num(A) = i - 2 * j

约束条件:    num(AB) <= n ; num(BA) <= m

转移方程:   f[i][j] = f[i - 1][j - 1] + f[i - 1][j]
                        前一步放A          前一步放B

注意到f[i]的状态只和f[i - 1]有关, 故可以用滚动数组优化空间

AC_code:

#include<bits/stdc++.h>
#define MAX 10005
#define ll long long
using namespace std;
const int mod = 1e9+7;
int n, m;
ll f[2][MAX];
int main() {
	while (~scanf("%d%d", &n, &m)) {
		f[0][0] = 1;
		for (int i = 1; i <= 2 * (n + m); i++) {
			int now = i % 2, pre = now ^ 1;
			for (int j = 0; j <= i; j++)//放j个A
				if (j <= n + m && i - j <= n + m) {
					f[now][j] = 0;
					if (2 * j - i <= n && i - 2 * j <= m) {
						if (j >= 1)//当前状态A的个数>=1  才有可能是上一个状态放了A
							(f[now][j] += f[pre][j - 1]) %= mod;
						if (i - j >= 1)//放B同理
							(f[now][j] += f[pre][j]) %= mod;
					}
				}
		}
		printf("%lld\n", f[(2 * (n + m)) % 2][n + m]);
	}
	return 0;
}