首页 > 代码库 > BZOJ 1566 管道取珠（DP）

BZOJ 1566 管道取珠（DP）

2024-07-08 23:59:10   220人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1566

题意：


思路：假设得到同一个序列S 的方案有ai=3，x,y,z，那么ai^2就是(x,x)(x,y)(x,z)(y,x)(y,y)(y,z)(z,x)(z,y)(z,z)，因此我们可以将原来的一套装置看做两套。f[i][j][p][q]表示从第一套装置的上面取i个下面取j个、从第二套装置的上面取p个下面取q个，且两套装置得到的两个序列相同的方案数，则答案就是f[n][m][n][m]。由于任何时候我们都是同时枚举两个装置中的，因此i+j=p+q在任意时刻都相等，因此只要三维就够了。

 

int f[N][N][N],n,m;char s1[N],s2[N];void up(int &x,int y){    x+=y;    if(x>=mod) x-=mod;}int main(){    RD(n,m);    RD(s1+1); RD(s2+1);    reverse(s1+1,s1+n+1);    reverse(s2+1,s2+m+1);    f[0][0][0]=1;    int i,j,k,t;    for(i=0;i<=n;i++) for(j=0;j<=m;j++) for(k=0;k<=n;k++)    {        t=i+j-k;        if(t<0||t>m) continue;        if(s1[i+1]==s1[k+1]) up(f[i+1][j][k+1],f[i][j][k]);        if(s1[i+1]==s2[t+1]) up(f[i+1][j][k],f[i][j][k]);        if(s2[j+1]==s1[k+1]) up(f[i][j+1][k+1],f[i][j][k]);        if(s2[j+1]==s2[t+1]) up(f[i][j+1][k],f[i][j][k]);    }    PR(f[n][m][n]);}

 

 

 


联系
我们