牛客多校一 E.ABBA

原题地址:https://ac.nowcoder.com/acm/contest/881/E

思路:定义表示有个,个的方案数.
首先,这样子定义,转移就很容易写,你就枚举当前串后面再添一个还是,所以也就是

dp[i + 1][j] += dp[i][j];
dp[i][j + 1] += dp[i][j];

所以现在的问题是如何确定一个串是由个并且由m个

我们考虑之前定义的前缀个和个,进一步思考如果,那么这个串至少会产生个(因为如果在某个前缀的时候你,那么必然有个只能与后面的匹配),同理,也是一样的.

所以对于题目中描述的个,个,只需要时候注意合法的转移就可以了.也就是说并且,每次转移的注意一下就可以了.

#include <bits/stdc++.h>
#define eps 1e-8
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)+1
#define CLR(x,y) memset((x),y,sizeof(x))
#define ***(x) cerr << #x << "=" << x << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int seed = 131;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
ll dp[2004][2005];
//dp[i][j]表示前缀有i个A,有j个B的方案数
int main() {
    int n, m;
    while (~scanf("%d%d", &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 <= m + n; j++) {
                if (i - j < n)dp[i + 1][j] += dp[i][j];
                if (j - i < m)dp[i][j + 1] += dp[i][j];
                dp[i + 1][j] %= mod;
                dp[i][j + 1] %= mod;
            }
        }
        printf("%lld\n", dp[n + m][n + m]);
    }
    return 0;
}