首页 > 学院 > 开发设计 > 正文

bzoj 1566: [NOI2009]管道取珠 (DP)

2019-11-11 06:25:43
字体:
来源:转载
供稿:网友

1566: [NOI2009]管道取珠

Time Limit: 20 Sec  Memory Limit: 650 MBSubmit: 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 1ABB

Sample Output

5

HINT

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

Source

[Submit][Status][Discuss]

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define N 503#define p 1024523using 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]);}


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表