鏈接：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.

* $\mathrm{0\le n,m\le 1030\le n,m\le 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;//嘗試插入Aint needAB = n-cA;//A后面連接多少個ABif(needAB>n+m-j)continue;elsedp[i+1][j] = (dp[i+1][j]+dp[i][j])%mod;int cB = j;//嘗試插入Bint needBA = m-cB;//B后面連接多少個BAif(needBA>n+m-i)continue;elsedp[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

總結

以上是生活随笔為你收集整理的2019牛客暑期多校训练营（第一场）E题 ABBA（DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。