首页 > 代码库 > bzoj1566 [NOI2009]管道取珠
bzoj1566 [NOI2009]管道取珠
Description
Input
第一行包含两个整数n, m，分别表示上下两个管道中球的数目。 第二行为一个AB字符串，长度为n，表示上管道中从左到右球的类型。其中A表示浅色球，B表示深色球。 第三行为一个AB字符串，长度为m，表示下管道中的情形。
Output
仅包含一行，即为 Sigma(Ai^2) i从1到k 除以1024523的余数。
Sample Input
2 1
AB
B
AB
B
Sample Output
5
HINT
样例即为文中(图3)。共有两种不同的输出序列形式，序列BAB有1种产生方式，而序列BBA有2种产生方式，因此答案为5。
【大致数据规模】
约30%的数据满足 n, m ≤ 12；
约100%的数据满足n, m ≤ 500。
正解：$dp$。
思路比较巧妙。注意到$a_{i}$平方以后不好处理，那么我们可以下意识地想到，其实这就是$4$个管道输出序列相同的一种情况。两个管道相同的有$a_{i}$种方案，那么$4$个管道方案组合，自然也就有$a_{i}^{2}$种方案了。
接下来的事就很简单了，设$f[i][j][k][l]$表示$4$个管道分别丢了第$i$个，第$j$个，第$k$个，第$l$个珠子的相同序列方案数。因为我们要求两个序列要相同，所以很显然，$i+j=k+l$，于是我们可以去掉$l$这一维状态。然后我们判断$4$个珠子两两相等的情况转移就行了。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue>10 #include <stack>11 #include <map>12 #include <set>13 #define rhl (1024523)14 #define il inline15 #define RG register16 #define ll long long17 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)18 19 using namespace std;20 21 int f[510][510][510],n,m;22 char a[510],b[510];23 24 il int gi(){25 RG int x=0,q=1; RG char ch=getchar();26 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();27 if (ch==‘-‘) q=-1,ch=getchar();28 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();29 return q*x;30 }31 32 il void work(){33 n=gi(),m=gi(),scanf("%s",a+1),scanf("%s",b+1);34 reverse(a+1,a+n+1),reverse(b+1,b+m+1),f[0][0][0]=1;35 for (RG int i=0;i<=n;++i)36 for (RG int j=0;j<=m;++j)37 for (RG int k=0;k<=n && k<=i+j;++k){38 if (a[i]==a[k] && i && k){39 f[i][j][k]+=f[i-1][j][k-1];40 if (f[i][j][k]>=rhl) f[i][j][k]-=rhl;41 }42 if (a[i]==b[i+j-k] && i){43 f[i][j][k]+=f[i-1][j][k];44 if (f[i][j][k]>=rhl) f[i][j][k]-=rhl;45 }46 if (b[j]==a[k] && j && k){47 f[i][j][k]+=f[i][j-1][k-1];48 if (f[i][j][k]>=rhl) f[i][j][k]-=rhl;49 }50 if (b[j]==b[i+j-k] && j){51 f[i][j][k]+=f[i][j-1][k];52 if (f[i][j][k]>=rhl) f[i][j][k]-=rhl;53 }54 }55 printf("%d\n",f[n][m][n]); return;56 }57 58 int main(){59 File("pipe");60 work();61 return 0;62 }
bzoj1566 [NOI2009]管道取珠
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。