1566: [NOI2009]管道取珠
Time Limit: 20 Sec Memory Limit: 650 MB
Submit: 1659 Solved: 971Description
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
【分析】
我真是超级蠢啊。。。想了很久都想不到。。。。
一直二维DP搞来搞去搞不了！！！
注意求的是ai^2的和 平方！！！
也就是说，可以看成，两个人在取，问他们取出来的排列相同的方案有多少种。
那么本来的四维DP可以缩成三维，就直接递推就好了。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 #define Mod 1024523 8 #define Maxn 510 9 10 char s[Maxn]; 11 int a[Maxn],b[Maxn],f[Maxn][Maxn][Maxn]; 12 13 int main() 14 { 15 int n,m; 16 scanf("%d%d",&n,&m); 17 scanf("%s",s+1); 18 for(int i=1;i<=n;i++) a[i]=s[i]-'A';a[n+1]=10; 19 scanf("%s",s+1); 20 for(int i=1;i<=m;i++) b[i]=s[i]-'A';b[m+1]=100; 21 memset(f,0,sizeof(f)); 22 f[n][m][n]=1; 23 for(int i=n;i>=0;i--) 24 for(int j=m;j>=0;j--) 25 for(int k=n;k>=0;k--) 26 { 27 int l=i+j-k; 28 if(l<0||l>m||(i==n&&j==m)) continue; 29 // f[i][j][k]=0; 30 if(a[i+1]==a[k+1]) f[i][j][k]=(f[i][j][k]+f[i+1][j][k+1])%Mod; 31 if(a[i+1]==b[l+1]) f[i][j][k]=(f[i][j][k]+f[i+1][j][k])%Mod; 32 if(b[j+1]==a[k+1]) f[i][j][k]=(f[i][j][k]+f[i][j+1][k+1])%Mod; 33 if(b[j+1]==b[l+1]) f[i][j][k]=(f[i][j][k]+f[i][j+1][k])%Mod; 34 } 35 printf("%d ",f[0][0][0]); 36 return 0; 37 }
2017-04-01 09:57:53