题目传送门
题目大意：
构造一个长为 $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
|
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 ()
{
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("%lldn",dp[(n+m)*2][1000]%mod);
}
return 0;
}
|
近期评论