题目链接

思路

首先我们知道\('A'\)在放了\(n\)个位置里面是没有约束的，\('B'\)在放了\(m\)个位置里面也是没有约束的，其他情况见下面情况讨论。

\(dp[i][j]\)表示放了\(i\)个\('A'\)和\(j\)个\('B'\)的方案数，然后考虑转移到下一个状态：

如果\(i\leq n\)，那么\('A'\)可以随意放；
如果\(j\leq m\)，那么\('B'\)可以随意放；
如果\(i> n\)，那么要放\('A'\)需要放了\('A'\)后多余的\('A'\)前面要有\('B'\)和它匹配，也就是说\(n-i-1\leq j\)；
如果\(j>m\)，那么要放\('B'\)需要放了\('B'\)后多余的\('B'\)前面有\('A'\)和它匹配，也就是说\(n-j-1\leq i\)。

代码实现如下

#include <set>

#include <map>

#include <deque>

#include <queue>

#include <stack>

#include <cmath>

#include <ctime>

#include <bitset>

#include <cstdio>

#include <string>

#include <vector>

#include <cstdlib>

#include <cstring>

#include <cassert>

#include <iostream>

#include <algorithm>

#include <unordered_map>

using namespace std;

typedef long long LL;

typedef pair<LL, LL> pLL;

typedef pair<LL, int> pLi;

typedef pair<int, LL> pil;;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define lson rt<<1

#define rson rt<<1|1

#define lowbit(x) x&(-x)

#define name2str(name) (#name)

#define bug printf("*********\n")

#define debug(x) cout<<#x"=["<<x<<"]" <<endl

#define FIN freopen("D://Code//in.txt","r",stdin)

#define IO ios::sync_with_stdio(false),cin.tie(0)

const double eps = 1e-8;

const int mod = 1e9 + 7;

const int maxn = 1e5 + 7;

const double pi = acos(-1);

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3fLL;

int n, m;

LL dp[2007][2007];

int main() {

    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 <= n + m; ++j) {

                if(i < n + j) dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % mod;

                if(j < m + i) dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % mod;

            }

        }

        printf("%lld\n", dp[n+m][n+m]);

    }

    return 0;

}

巴特西

2019年牛客多校第一场 E题 ABBA DP

题目链接

思路

代码实现如下

最新文章

热门文章