题解 P1758 【[NOI2009]管道取珠】

ModestCoder_ · 2019-09-08 15:52:17 · 题解

首先转化问题

两个人在两个独立的装置里取球，输出队列相同的方案数因为对于每一种输出队列，第一个人有$a_i$种方案，第二个人有$a_i$种方案那么两个人输出队列相同的方案总数就是$a_i^2

然后就是一个很简单的dp题目了

然后已知答案就是$dp_{n+m,n,n}

然后思考如何转状态转移，根据dp状态的定义，当目前两个人取的球的个数相同才可能发生转移，然后讨论两个人当前从那根管道取的球

a_i=a_j:dp_{k,i,j}<-dp_{k-1,i-1,j-1}
a_i=b_{k-j}:dp_{k,i,j}<-dp_{k-1,i-1,j}
b_{k-i}=a_j:dp_{k,i,j}<-dp_{k-1,i,j-1}
b_{k-i}=b_{k-j}:dp_{k,i,j}<-dp_{k-1,i,j}

注意一下细节就行了

最后考虑时空间的复杂度，时间上O(n^3)没毛病

空间上有那么一点问题，但是看到第一维可以滚动掉，放心了

Code：

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define maxn 510
using namespace std;
const int qy = 1024523;
int n, m, a[maxn], b[maxn], dp[2][maxn][maxn];

int get(){
    char c = getchar();
    for (; c != 'A' && c != 'B'; c = getchar());
    return c == 'A';
}

void upd(int &x, int y){ if ((x += y) >= qy) x -= qy; }

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) a[i] = get();
    for (int i = 1; i <= m; ++i) b[i] = get();
    reverse(a + 1, a + 1 + n);
    reverse(b + 1, b + 1 + m);
    dp[0][0][0] = 1;
    for (int k = 1; k <= n + m; ++k){
        int now = k & 1, pre = now ^ 1;
        for (int i = 0; i <= n; ++i)
            for (int j = 0; j <= n; ++j) dp[now][i][j] = 0;
        for (int i = max(0, k - m); i <= min(n, k); ++i)
            for (int j = max(0, k - m); j <= min(n, k); ++j){
                if (i && j && a[i] == a[j]) upd(dp[now][i][j], dp[pre][i - 1][j - 1]);
                if (i && k - j && a[i] == b[k - j]) upd(dp[now][i][j], dp[pre][i - 1][j]);
                if (j && k - i && b[k - i] == a[j]) upd(dp[now][i][j], dp[pre][i][j - 1]);
                if (k - i && k - j && b[k - i] == b[k - j]) upd(dp[now][i][j], dp[pre][i][j]);
            }
    }
    printf("%d\n", dp[(n + m) & 1][n][n]);
    return 0;
}