2019牛客多校第一场

发表于 | 更新于 | 分类于
本文字数： 6.9k

E. ABBA

题意：

  你拥有一个长度为\(2*(n+m)\)的字符串，它含有\(n+m\)个\(A\)，以及\(n+m\)个\(B\)，你把个字符串给分解，最后可以得到\(n\)个子序列\(AB\)与\(m\)个子序列\(BA\)，问这个字符串有多少种，最终结果对（\(10^9+7\)）取余；比如\(\underline{A}\space\underline{BA}\space\underline{B}\)，第一个\(A\)与最后一个\(B\)匹配，中间的\(AB\)进行匹配，这就是对应\(n=1,m=1\)的一种合法的字符串；

分析：

  使用\(dp[i][j]\)表示含有\(i\)个\(A\)和\(j\)个\(B\)的合法字符串的个数，目标为\(dp[n+m][n+m]\)；

  首先，一个事实是，对于一个合法的含\(n\)个\(AB\)含\(m\)个\(BA\)的串，考虑它的前\(n\)个\(A\)作为\(AB\)的\(A\)，考虑前\(m\)个\(B\)作为\(BA\)的\(B\);

  然后，对于\(i、j\)，考虑在当前位置插入\(A\)，或者在当前位置插入\(B\)，那么我们有转移方程： \[dp[i][j]=dp[i-1][j]+dp[i][j-1]\]

  然而中间并非所有的状态都合法；比如对于\(n=1,m=1\)的情况，\(AABB\)是不可行的，它没有被添加到最后的结果中，原因在于，在状态转移的过程中，从\(A\)到\(AA\)的转移是不可行的；第一个\(A\)用作\(AB\)的A，而对于第二个\(A\)来说，由于此时\(AB\)的\(A\)数量已经够了，它应该是\(BA\)的\(A\)，所以它前面必须有\(B\)，那么\(AA\)显然是不可行的；

  如果在之前情况基础上，在最后位置插入\(A\)，那么\(B\)的数量\(j\)必须不小于，\(A\)的数量\(i\)减去组成\(n\)个\(AB\)的\(A\)的数量，即\(i-n<=j\)，如果插入\(B\)，也同理；

代码：

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
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=2010;
int n,m;
ll p=1e9+7;
ll dp[maxn][maxn];
int main(){
    while(cin>>n>>m){
        for(int i=0;i<=n+m;i++){
            for(int j=0;j<=n+m;j++)dp[i][j]=0;
        }
        dp[0][0]=1;
        for(int i=0;i<=n+m;i++){
            for(int j=0;j<=n+m;j++){
                if(i+1<=j+n){
                    dp[i+1][j]=(dp[i+1][j]+dp[i][j])%p;
                }
                if(j+1<=i+m){
                    dp[i][j+1]=(dp[i][j+1]+dp[i][j])%p;
                }
            }
        }
        printf("%lld\n",dp[n+m][n+m]);
    }
}