[2019牛客暑期多校训练营(第一场)- E题]ABAB

题目传送门

题目大意:

构造一个长为 $2*(n+m)$ 的字符串,使得能从中按顺序挑出 $n$ 个”AB”子串和 $m$ 个”BA”子串,问这样的字符串一共有多少个。

一个似乎比较明显的dp问题,类似于括号配对。

二维dp,dp[i][j],表示前i个字符,字母A和字母B的差为j个,然后就可以进行dp了。

代码如下:

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
28
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=1000000+10;
const ll mod=1000000007;
const int INF=0x3f3f3f3f;
ll dp[1000*4+10][1000*4];
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m)){
for(int i=1;i<=(n+m)*2;i++){
for(int j=1000-m-1;j<=1000+n+1;j++){
dp[i][j]=0;
}
}
dp[0][1000]=1;
for(int i=1;i<=(n+m)*2;i++){
for(int j=1000-m;j<=1000+n;j++){
dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
dp[i][j]%=mod;
}
}
printf("%lld\n",dp[(n+m)*2][1000]%mod);
}
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------