menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[DP]BZOJ1566(NOI2009)【管道取珠】题解
apps BZOJ
local_offer 查看标签
comment 0 条评论

题目概述

有两个管道,第一个有 $n$ 个黑白珠子,第二个有 $m$ 个黑白珠子,每次可以从一个管道取出最靠管道口的珠子。假设有 $k$ 中取珠子的方法,第 $i$ 种方案的方案数为 $a_i$ 那么贡献为 $\sum_{i=1}^{k}a_i^2$ 。求贡献。

解题报告

开平方可以理解为每种方案都和相同的方案有贡献,所以我们可以认为有两个取珠游戏同时进行,且只有两个游戏取出来的方案一样时才有贡献,也就是说:

定义 $f[i][j][k][t]$ 表示第一个游戏的第一个管道取了 $i$ 个,第二个管道取了 $j$ 个;第二个游戏的第一个管道取了 $k$ 个,第二个管道取了 $t$ 个的贡献,那么就只有当每次取出来的珠子颜色相同才能转移,就变成了很简单的DP。

实际上因为 $i+j=k+t$ ,所以只需要 $f[i][j][k]$ 就行了。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
const int maxn=500,MOD=1024523;

int n,m,a[maxn+5],b[maxn+5];
int f[maxn+5][maxn+5][maxn+5];

inline char getupr() {char ch=getchar();while (!isupper(ch)) ch=getchar();return ch;}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=n;i;i--) a[i]=getupr()-'A';
    for (int i=m;i;i--) b[i]=getupr()-'A';
    f[0][0][0]=1;
    for (int i=0;i<=n;i++)
        for (int j=0;j<=m;j++)
            for (int k=0,t=i+j;k<=i+j&&k<=n;k++,t--){
                int &F=f[i][j][k];
                if (i&&t&&a[i]==b[t]) AMOD(F,f[i-1][j][k]);
                if (i&&k&&a[i]==a[k]) AMOD(F,f[i-1][j][k-1]);
                if (j&&t&&b[j]==b[t]) AMOD(F,f[i][j-1][k]);
                if (j&&k&&b[j]==a[k]) AMOD(F,f[i][j-1][k-1]);
            }
    return printf("%d\n",f[n][m][n]),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up