2019牛客暑期多校训练营（第一场）

https://ac.nowcoder.com/acm/contest/881/E
从dp的角度来看是比较正常的。无后效性来源于前面只要的合法的方案分配，那么对后面造成的影响就只有A,B的数目。
从贪心的角度看，前n个A必定是给AB用的，前m个B必定是给BA用的。否则假如有一个BA用了一个前n个A里的A，那么可以把这个A和后面的某个A互换所在的组。

dp参考JHSeng大佬的题解。
设 (dp[i][j]) 表示放置 (i) 个A，放置 (j) 个B的合法方案数。显然 (dp[0][0]=1) ，转移有 (dp[i][j]=dp[i-1][j]+dp[i][j-1]) 。
但并不是每次放A和放B都可以转移到合法方案数。什么情况下是不合法的呢？
那么，
当 (i<=n) 的时候，再放的A一定可以给AB用，放 (dp[i-1][j]) 。
当 (i>n) 的时候，这时放的A一定是给BA用的，限制是有没有足够多的B在这个前面，也就是 (j>(i-n)) 时，放 (dp[i-1][j]) 。

另一个也是同理。

---

还卡memset。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define ERR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {cerr << "
";}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << "=" << a << ", ";
    err(++it, args...);
}

ll dp[2005][2005];

const int mod=1e9+7;

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
    //freopen("Yinku.out", "w", stdout);
#endif // Yinku
    int n,m;
    while(~scanf("%d%d", &n,&m)) {
        for(int i=0;i<=n+m;i++){
            memset(dp[i],0,sizeof(dp[i][0])*(n+m+1));
        }
        dp[0][0]=1;
        for(int i=0; i<=n+m; i++) {
            for(int j=0; j<=n+m; j++) {
                if((i+1<=n+m)&&(i+1<=n||(min(j,m)>=(i+1-n))))
                    dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
                if((j+1<=n+m)&&(j+1<=m||(min(i,n)>=(j+1-m))))
                    dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;
            }
        }
        printf("%lld
",dp[n+m][n+m]);
    }
}

---

从组合的角度看。
https://blog.csdn.net/qq_39239844/article/details/96475068
总的方案数=从(n+m)2个位置选(n+m)个位置放A的方案数。
不合法的方案数=从(n+m)2个位置选(n-1)个位置放A的方案数+从(n+m)*2个位置选(m-1)个位置放B的方案数