【题解】NOI2009管道取珠

　　又是艰难想题的一晚，又是做不出来的一题 (；д；) 好想哭啊……

　　这题最关键的一点还是提供一种全新的想法。看到平方和这种东西，真的不好dp。然而我一直陷在化式子的泥潭中出不来。平方能够联想到什么？原本的方案的乘积。将两部分相乘，我们能够联想到这是两个人在取珠，求他们取出来的珠子颜色序列相同的方案数之和。（第一个人要得到 \(x\) 这种颜色方案有\(a_{x}\)种，第二个人也一样。所以一共为 \({a_{x}}^{2}\) 种。到这里，应该就很容易了。虽然看了题解之后恍然大悟，然而深深地明白目前的自己与做出此题之间仍然是有着无法逾越的鸿沟的。唯有坚持努力下去，勤加积累才能够等到柳暗花明的一天 (≧∇≦)ﾉ

　　注意滚动数组哦。

#include <bits/stdc++.h>

using namespace std;

#define maxn 505

#define mod 1024523

int n, m, a[maxn], b[maxn];

int pre = , now = , f[][maxn][maxn];

char c;

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

void up(int &x, int y) { x = (x + y) % mod; }

int main()

{

    int n = read(), m = read();

    for(int i = ; i <= n; i ++)

    {

        cin >> c;

        if(c == 'B') a[n - i + ] = ;

    }

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

    {

        cin >> c;

        if(c == 'B') b[m - i + ] = ;

    }

    f[][][] = ;

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

    {

        int lim1 = min(i, n), lim2 = min(i, n);

        for(int j = ; j <= lim1; j ++)

            for(int k = ; k <= lim2; k ++)

            {

                f[now][j][k] = ;

                int x = i - j, y = i - k;

                if(x > m || y > m) continue;

                if(a[j] == a[k]) up(f[now][j][k], f[pre][j - ][k - ]);

                if(a[j] == b[i - k]) up(f[now][j][k], f[pre][j - ][k]);

                if(b[i - j] == a[k]) up(f[now][j][k], f[pre][j][k - ]);

                if(b[i - j] == b[i - k]) up(f[now][j][k], f[pre][j][k]);

            }

        swap(pre, now);

    }

    printf("%d\n", f[pre][n][n]);

    return ;

}

巴特西

【题解】NOI2009管道取珠

最新文章

热门文章