链接：https://ac.nowcoder.com/acm/contest/881/E
题目描述
Bobo has a string of length 2(n + m) which consists of characters `A` and `B`. The string also has a fascinating property: it can be decomposed into (n + m) subsequences of length 2, and among the (n + m) subsequences n of them are `AB` while other m of them are `BA`.
Given n and m, find the number of possible strings modulo
(109+7)(109+7).
输入描述:
The input consists of several test cases and is terminated by end-of-file.Each test case contains two integers n and m.*
0≤n,m≤1030≤n,m≤103* There are at most 2019 test cases, and at most 20 of them has max{n,m}>50max{n,m}>50.
输出描述:
For each test case, print an integer which denotes the result.
示例1
输入
复制
1 2
1000 1000
0 0
输出
复制
13
436240410
1
思路：一开始讨论，想的是个找规律（虽然我读不懂题，也猜不对）。后来看了题解，才知道是个dp。 是酱紫的，题目说有N个AB，M个BA，那你就要注意到（A的个数）=（B的个数），尝试在A或B后面加A、B，但是这样很麻烦，所以就直接在A后面加AB，在B后面加BA。其中：DP的时候（A的个数 ）<=（n+B的个数），（B的个数 ）<=（m+A的个数）。首先你要选取A在开头或是B在开头，然后选他们后面跟了什么（A后面尝试加AB，试试有多少种可能）（B后面尝试加BA，试试有多少种可能），然后把两者相加，就是答案。*我队友：“来自那啥的肯定”
#include <cstdio>
#include <iostream>
#include <
string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#define ll long long
int mod = 1e9+
7;
int dp[
5000+
8][
5000+
8];
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++)
//A的个数
{
for(
int j =
0; j <= m+n; j++)
//B的个数
{
int cA = i;
//尝试插入A
int needAB = n-cA;
//A后面连接多少个AB
if(needAB>n+m-j)
continue;
else
dp[i+
1][j] = (dp[i+
1][j]+dp[i][j])%
mod;
int cB = j;
//尝试插入B
int needBA = m-cB;
//B后面连接多少个BA
if(needBA>n+m-i)
continue;
else
dp[i][j+
1] = (dp[i][j+
1]+dp[i][j])%
mod;
}
}
printf("%d\n", dp[n+m][n+
m]);
}
return 0;
}
转载于:https://www.cnblogs.com/RootVount/p/11228164.html
相关资源：JAVA上百实例源码以及开源项目
