https://ac.nowcoder.com/acm/contest/881/E
题意：构造一个长度为2*(n+m)的AB串，使这个串可以划分成n和“AB”的子序列和m个“BA”的子序列，求方案数量
思路：
首先注意：子序列不是子串 只需要相对位置正确 不需要是连续的
确定状态：求什么就设什么，设dp[i][j]为前i个A+前j个B可以组合的合法字符串的数量，那么我们最终要求的dp[n+m][n+m]就是本题的解
对于一个合法的字符串，明确一个性质：
前n个A必定是“AB”的A，同理，可以得到前m个B必定是“BA”的B
可以简单证明一下：如果前n个A里，有一个是“BA”的A，那么这个A后边肯定还存在一个A可以给这个B组合在一起形成“BA”，那么这个A就从原本的“BA”里A变成“AB”里的A，这样就可以得出前n个A都是“AB”的A的结论
之后就是枚举下一个字符是A 还是B
下一个字符放A：
如果i < n，由前n个A必定是“AB”的A可知可以放A
如果i >= n，这个时候就要看B的个数了 ，要确保这个A能给前面的B当"BA"用，那么当前"BA"里需要的A是min(j, m)。所以i - n < min(j,m)成立时，也可以放A。
解释一下为什么是min(j,m), 如果j < m，min(j,m) = j,那么前j个B需要j个A构成“BA”，如果j > m,min(j,m) = m,前m个B都需要m个A构成“BA”。
下一个字符放B：
和放A同理。
如果j < m，由前m个B必定是“BA”的B可知可以放B
如果j >= m，这个时候就要看A的个数了 ，要确保这个B能给前面的A当"AB"用，那么当前"AB"里需要的B是min(i, n)。所以j - m < min(i,n)成立时，也可以放B。
代码
#include <iostream> #include <cstring> #include <algorithm> #include <string> #define ll long long #include <set> using namespace std; const int Max = 2010; const int mod = 1e9+7; ll n,m; ll dp[Max][Max]; int main(){ while(cin>>n>>m){ int s = n+m; for(int i = 0 ; i <= s; i++){ for(int j = 0 ; j <= s; j++){ dp[i][j] = 0; } } dp[0][0] = 1; for(ll i = 0 ; i <= s; i++){ for(ll j = 0 ; j <= s; j++){ //放A if(i < n || (i-n) < min(j,m)){ dp[i+1][j] = (dp[i+1][j] + dp[i][j])%mod; } //放B if(j < m || (j-m) < min(i,n)){ dp[i][j+1] = (dp[i][j+1] + dp[i][j])%mod; } } } cout<<dp[s][s]<<"\n"; } return 0; }
