[比赛补题][DP][递推计数][思维] 牛客2019多校 第一场 E ABBA

比赛时候：第一眼这不就DP吗，第二眼欸这东西怎么转移啊。。gg

当时迷了一直在想以AB和BA的数目为下标推，但是这样会有很多去重的问题。。。于是就没整出来，后来滚去推高数题了

看了叉姐的一句话题解大概懂了，推的时候直接用x和y的数目做下标，这样首先可以避免重复的问题。也就是设dp[i][j]为i个A，j个B时可用的前缀有多少种。这里面最重要的就是这个“可用的”怎么确定。这里的判断写出来很简单(i-j<=n&&j-i<=m).为什么是这样的呢？现在来考虑一个前缀，什么时候我们可以判断这个前缀一定不能作为最终答案中的某一个方案的前缀（也就是对最终答案没有任何贡献）？首先考虑凑AB，要用这个前缀的话，最终的结果是在他后面再补上(n+m-i)个A和(n+m-j)个B，注意这里的后面的排列并没有确定，也就是说我为了用到这个前缀（使答案+=它这种情况），可以尽力的去想办法摆布后面的A和B使得满足要求。那么有一个结论是在i-j>n的时候无论后面如何摆都满足不了要求：这个前缀至少可以配成j-1个AB或者BA，在加一个AB或者BA，然后如果i比j多了n个以上，那么意味着这多出来的i-j个A跟后面的配对只能配AB了，这样的话AB的总数就超过了n，由于AB和BA的总数确定的，这时候就一定不满足要求了；反之如果i-j<=n，则一定可以通过后面的调整来满足n个AB，m个BA的要求，可以自己试试看，只要注意到AB和BA的互换就行了。比如ABAB可以看出俩AB也可以看出一个AB一个BA（中间的）。。

然后dp边界是dp[i<=n][0]=1,dp[0][j<=m]=1，这个很好理解，全是A或者全是B就只有一种情况的。。。

这题还有点卡常，dp每次不要都memset，否则会tle

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int maxn=1e3+5;
const int mod=1e9+7;

ll dp[maxn<<1][maxn<<1];

void add(ll& a,ll b){
    if(a+b>mod) a=(a+b-mod);
    else a=a+b;
}

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;
                if((i==0&&j<=m) ||(j==0&&i<=n)){
                    dp[i][j]=1;
                    continue;
                }
                if(i-j>n||j-i>m) continue;
                add(dp[i][j],dp[i-1][j]);
                add(dp[i][j],dp[i][j-1]);
            }
        printf("%lld\n",dp[n+m][n+m]);
    }
    return 0;
}