bzoj 1566: [NOI2009]管道取珠 （DP）

1566: [NOI2009]管道取珠

Time Limit: 20 Sec   Memory Limit: 650 MB Submit: 1494   Solved: 850 [ Submit][ Status][ Discuss]

Description

 

Input

第一行包含两个整数n, m，分别表示上下两个管道中球的数目。 第二行为一个AB字符串，长度为n，表示上管道中从左到右球的类型。其中A表示浅色球，B表示深色球。 第三行为一个AB字符串，长度为m，表示下管道中的情形。

Output

仅包含一行，即为 Sigma(Ai^2) i从1到k 除以1024523的余数。

Sample Input

2 1 AB B

Sample Output

5

HINT

样例即为文中(图3)。共有两种不同的输出序列形式，序列BAB有1种产生方式，而序列BBA有2种产生方式，因此答案为5。  【大致数据规模】 约30%的数据满足 n, m ≤ 12；  约100%的数据满足n, m ≤ 500。

Source

[ Submit][ Status][ Discuss]

题解：DP

这道题有一个很奇妙的转换，Sigma(Ai^2) 比好直接求，但是我们可以看成是两个人在同时操作，最终得到的序列相同的方案数。

对于方案数我们就可以用dp来求解了

f[i][j][k]表示的是第一个人从上管道取了i个珠，从下管道取了j个珠，第二个人从上管道取了k个珠（还隐含着以为就是第二个人从下管道取了i+j-k个珠）

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 503 #define p 1024523 using namespace std; int n,m,f[N][N][N]; char s[N],s1[N]; int main() { freopen("a.in","r",stdin); scanf("%d%d",&n,&m); scanf("%s",s+1); scanf("%s",s1+1); //f[0][0][0]=1; for (int i=0;i<=n;i++) for (int j=0;j<=m;j++) for (int k=0;k<=n;k++) { if (i==0&&j==0&&k==0) { f[0][0][0]=1; break; } int l=i+j-k; if (l<0) break; if (i-1>=0&&k-1>=0&&s[i]==s[k]) f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1])%p; if (i-1>=0&&l-1>=0&&s[i]==s1[l]) f[i][j][k]=(f[i][j][k]+f[i-1][j][k])%p; if (j-1>=0&&k-1>=0&&s1[j]==s[k]) f[i][j][k]=(f[i][j][k]+f[i][j-1][k-1])%p; if (j-1>=0&&l-1>=0&&s1[j]==s1[l]) f[i][j][k]=(f[i][j][k]+f[i][j-1][k])%p; } printf("%d\n",f[n][m][n]); }