正题

题目链接:https://www.luogu.com.cn/problem/P1758

题目大意

给出一个大小为\(n\)和一个大小为\(m\)的栈，每次选择一个栈弹出栈顶然后记录这个字母，求所有弹出序列的弹出方案的二次方和。

\(1\leq n,m\leq 500\)

解题思路

二次方和可以看为取出方案相同的对数。

然后就是很简单的\(dp\)了，设\(f_{i,j,k}\)表示都取出了\(i\)个，在第一个栈里分开取了\(j/k\)个，然后滚动。

时间复杂度\(O(nmn^2)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=510,P=1024523;

int n,m,f[N*2][N][N];

char s[N],t[N];

int main()

{

	scanf("%d%d",&n,&m);

	scanf("%s",s+1);

	scanf("%s",t+1);

	f[0][0][0]=1;

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

		for(int j=0;j<=min(n,i);j++)

			for(int k=0;k<=min(n,i);k++){

				f[i&1][j][k]=0;

				if(s[j]==s[k]&&j&&k)(f[i&1][j][k]+=f[~i&1][j-1][k-1])%=P;

				if(s[j]==t[i-k]&&j&&i-k)(f[i&1][j][k]+=f[~i&1][j-1][k])%=P;

				if(t[i-j]==s[k]&&k&&i-j)(f[i&1][j][k]+=f[~i&1][j][k-1])%=P;

				if(t[i-j]==t[i-k]&&i-j&&i-k)(f[i&1][j][k]+=f[~i&1][j][k])%=P;

			}

	printf("%d\n",f[(n+m)&1][n][n]);

	return 0;

}

巴特西

P1758-[NOI2009]管道取珠【dp】

正题

题目大意

解题思路

code

最新文章

热门文章