https://ac.nowcoder.com/acm/contest/881/E
题目大意:
让你构造一个字符串(长度2n+2m,全部由'A'和’B'构成),字符串可以拆分为n个"AB"串,m个"BA"串,
问这样的串有多少种.
比赛的时候完全没想到怎么搞,只想到可以用想类似括号序列的方法:每个A代表1,B代表-1,
于是一个AB串就具有一个前缀和
dp[i]代表串的前缀和为i的方法数
没想太明白,其实这样也可以搞,但是要加一维:dp[i][j]代表前缀和为[i]使用了[j]个A的前缀方案数
其实跟题解差不多:
这道题说起来其实并不难:就是比赛时太紧张了再加上我平时做这种题也不多:
这道DP题其实主要就是要限制状态转移条件:
当然前提要用到一个贪心思想:如果前面用到了A,先把A用作"AB"中的A,如果用到了B,先把B用作"BA"中的B
于是....得到了状态转移的方法:
设dp[i][j]为前面使用了i个A,j个B之后,后面字符串的方案数:dp[n+m][n+m]=1;dp[0][0]=ans;
首先你可以假设枚举下一个字符的时候你可以随便枚举:
这样dp[i][j]=dp[i+1][j]+dp[i][j+1]
但是这样肯定还不够,比如这样你会算出dp[n+m][0]有一个值,你的算法就变成了算n+m个A,n+m个B组成的AB字符串有多少种
所以只要加个限制条件就好了,人为的把不合法的方案数剔除掉。
首先想一下一个方案是什么:
一个方案->在这题里就是一个字符串->可以表示为(i,j)对从(0,0)变化为(n+m,n+m)的路径数
如果不加限制,所有路径数就是n+m个A,n+m个B的字符串有多少种。
所以我们要加的限制就是要剪掉路径的前缀存在 符号序列前缀和(A=1,B=-1)s ,s>n或者s<-m的,因为这样就肯定AB不够或者BA不够
但是我们肯定不可能对每一条路径追根求源的,于是我们需要判断某个特定的点(i,j)是不是非法的,这是就可以用到上述的贪心思
想:判定(i,j)是否合法的时候,就先把min(i,n)个A放在AB的A中,min(j,m)个B放在BA的B中,剩下来的A或者B就拿去做后面的那个字符。加入制造出的后面的空位不够放多出来的字符,那就是非法的,强制把这条路径断掉:dp[i][j]=0;
于是代码就出来了:
/////////////////////////////////////////Info/////////////////////////////////////////////////
//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//循环控制
#define CLR(a) memset((a),0,sizeof(a))
#define F(i,a,b) for(int i=a;i<=int(b);++i)
#define F2(i,a,b) for(int i=a;i>=int(b);--i)
#define RE(i,n) for(int i=0;i<int(n);i++)
#define RE2(i,n) for(int i=1;i<=int(n);i++)
//简化敲击
#define PII pair<int,int>
#define PDD pair<double,double>
#define PLL pair<long long ,long long>
#define PB push_back
#define MODY(n) (n%=mod)<0?n+=mod:n
#define MODED(n) ((n)<0?(n)%mod+mod:(n)%mod)
#define x first
#define y second
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const long long llinf = 0x3f3f3f3f3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
#define stdcpph
#define CPP_IO
#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#ifdef CPP_IO
#include<iostream>
#include<iomanip>
#include<string>
#else
#include<stdio.h>
#endif
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint> inline void IN(INint &x)
{
x = 0; int f = 1; char c; cin.get(c);
while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
x *= f;
}
template<typename INint> inline void OUT(INint x)
{
if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const int maxn = int(2e3+8);
const int mod = 1e9 + 7;
int dp[maxn][maxn];
int n, m;
int ok(int x, int y)
{
if (x > n + m || y > n + m)return 0;
int rx = n + m - x, ry = n + m - y;
if (x > n)
{
if (x - n > y)
return 0;
}
if (y > m)
{
if (y - m > x)
{
return 0;
}
}
return 1;
}
int dx[2] = { 0,1 }, dy[2] = { 1,0 };
void init()
{
//memset(dp, 0, sizeof(dp));
F(i, 0, n + m)F(j, 0, n + m)dp[i][j] = 0;
dp[n + m][n + m] = 1;
//F(i, 0, n+m)
F2(i,n+m,0)
{
//F(j, 0, n+m)
F2(j,n+m,0)
{
if (!ok(i, j))dp[i][j] = 0;
else
{
F(k, 0, 1)
{
int x = i + dx[k], y = j + dy[k];
if (ok(x, y))
{
dp[i][j] += dp[x][y];
if (dp[i][j] >= mod)dp[i][j] -= mod;
}
}
}
//cout << "dp[" << i << "][" << j << "] " << dp[i][j] << endl;
}
}
//F(i, 0, n)
//{
// F(j,0,n)
// cout << dp[i][j] << ' ';
// cout << endl;
//}
}
////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
int T(1), cas(0);
#ifdef CPP_IO// CPP_IO
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//cin >> T;
#else
//IN(T);
#endif
/////////////////////////////////////////////////////////////////////////////////////////////////
while (cas, T--,cin>>n>>m)
{
init();
cout << dp[0][0] << endl;
}
///////////////////////////////////////////////////////////////////////////////////////////////////
return 0;
}
//What to Debug
/*
-1.最好把全部warning都X掉,否则:https://vjudge.net/solution/19887176
0.看看自己是否有可能需要快读,禁endl
1.数组越界,爆int,浮点精度(查看精度是否达到题目要求,看有没有浮点数比较:eps),取模操作,初始化数组,边缘数据,输出格式(cas)
2.通读代码,代码无逻辑错误
3.读题,找到题意理解失误或算法错误
4.放弃
*/