ABBA

解题思路

用dp[i][j]来表示前i+j个字符中，有i个A和j个B的合法情况个数。我们可以让前n个A作为AB的A，因为如果我们用后面的A作为AB的A，我们一定也可以让前面的A对应那个B，同理，我们可以让前m个B作为BA的B。

接下来讨论转移方程。当i<=n时，这个A作为AB的A必然可以放进来，当i>n时，此时若放入A，则这个A是第i-n个BA的A，所以只有当i<=n+min(j,m)时才可以放入。同理，只有当j<=m或者j<=m+min(i,n)时才可放入这个B。

注意不能直接memset，会超时，要手写循环归0。

代码如下

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

inline int read(){

    int res = 0, w = 0; char ch = 0;

    while(!isdigit(ch)){

        w |= ch == '-', ch = getchar();

    }

    while(isdigit(ch)){

        res = (res << 3) + (res << 1) + (ch ^ 48);

        ch = getchar();

    }

    return w ? -res : res;

}

const int N = 2005;

const int mod = 1e9 + 7;

int dp[N][N];

int main()

{

    int n, m;

    while(scanf("%d%d", &n, &m) != EOF){

        for(int i = 0; i <= n + m; i ++){

            for(int j = 0; j <= n + m; j ++)

                dp[i][j] = 0;

        }

        for(int i = 0; i <= n; i ++) //前n个可以直接放A

            dp[i][0] = 1;

        for(int i = 0; i <= m; i ++)

            dp[0][i] = 1;

        for(int i = 1; i <= n + m; i ++){

            for(int j = 1; j <= n + m; j ++){

                if(i <= n + min(j, m)) //j,m都大于等于0

                    dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;

                if(j <= m + min(i, n))

                    dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod;

            }

        }

        printf("%d\n", dp[n + m][n + m] % mod);

    }

    return 0;

}

巴特西

2019牛客多校第一场 E-ABBA（dp）

ABBA

解题思路

代码如下

最新文章

热门文章