首页 > 代码库 > bzoj1566【Noi2009】管道取珠

bzoj1566【Noi2009】管道取珠

2024-09-01 19:21:42   216人阅读

题意：http://www.lydsy.com/JudgeOnline/problem.php?id=1566

　　　两个栈不断pop，共C（n+m，n）种，ai表示每个相同序列的方案数，求∑(ai^2)

sol  ：首先，将相同的序列看做两个人选取后相同的方案数

　　　考虑Dp，dp[i][j][k][l]表示第一个人从上面选i个，下面选j个，第二个人上k个下l个的答案

　　　显然第四维状态可以由前三维决定

　　　不过还是不太好转移，将状态换为dp[i][j][k]表示选了i个点，第一个人从上面选了j个，第二个人从上面选了k个的答案

　　　这样的话第一维还可以用滚动数组优化

　　　所以转移如下(tmp=0或1)

if(a[j+1]==b[i-k+1]) dp[!tmp][j+1][k]=(dp[!tmp][j+1][k]+dp[tmp][j][k])%p;
if(b[i-j+1]==a[k+1]) dp[!tmp][j][k+1]=(dp[!tmp][j][k+1]+dp[tmp][j][k])%p;
if(b[i-j+1]==b[i-k+1]) dp[!tmp][j][k]=(dp[!tmp][j][k]+dp[tmp][j][k])%p;
if(a[j+1]==a[k+1]) dp[!tmp][j+1][k+1]=(dp[!tmp][j+1][k+1]+dp[tmp][j][k])%p;

　　　代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int Mx=510;
const int p=1024523;
int n,m,a[Mx],b[Mx],dp[2][Mx][Mx];
char c1[Mx],c2[Mx];
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s%s",c1,c2);
    for(int i=0;i<n;i++) a[n-i]=c1[i]-‘A‘;
    for(int i=0;i<m;i++) b[m-i]=c2[i]-‘A‘;
    dp[0][0][0]=1;
    for (int i=0;i<n+m;i++)
    {
        int tmp=i%2;
        for(int j=0;j<=n&&j<=i;j++)  
            for(int k=0;k<=n&&j<=i;k++)  
                if(dp[tmp][j][k]!=0)
                {  
                    if(a[j+1]==b[i-k+1]) dp[!tmp][j+1][k]=(dp[!tmp][j+1][k]+dp[tmp][j][k])%p;
                    if(b[i-j+1]==a[k+1]) dp[!tmp][j][k+1]=(dp[!tmp][j][k+1]+dp[tmp][j][k])%p;
                    if(b[i-j+1]==b[i-k+1]) dp[!tmp][j][k]=(dp[!tmp][j][k]+dp[tmp][j][k])%p;
                    if(a[j+1]==a[k+1]) dp[!tmp][j+1][k+1]=(dp[!tmp][j+1][k+1]+dp[tmp][j][k])%p;
                    dp[tmp][j][k]=0;        
                }
    }
    cout<<dp[(n+m)%2][n][n]<<endl; 
    return 0;
}

bzoj1566【Noi2009】管道取珠


联系
我们