【bzoj1566】【管道取珠】竟然是dp题(浅尝ACM-E)

【bzoj1566】【管道取珠】竟然是dp题(浅尝ACM-E)

[pixiv] https://www.pixiv.net/member_illust.php?mode=medium&illust_id=61891436

向大(hei)佬(e)*学(di)习(tou)

Description

【bzoj1566】【管道取珠】竟然是dp题(浅尝ACM-E)

【bzoj1566】【管道取珠】竟然是dp题(浅尝ACM-E)

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。

一眼就被sigma吓傻了,以为是一道数论题,分析来分析去,好不容易把题目中的等式理解了,却对着ai^2不知所措

(以下是大佬把我讲懂的)

仔细分析,ai表示第i种输出序列的方案数,那么ai^2就是ai*ai,感觉像不像两个人玩这个游戏得到相同输出的方案数?由此一来就有些思路可循了

我们设dp[i][j][k][l]表示第一个人从上排取i个,下排取j个,第二个人上排取k个,下排取l个。转移方程即为(a[]为上排b[]为下排):

1、a[i]==a[k] , dp[i][j][k][l]+=dp[i-1][j][k-1][l];

2、a[i]==b[l] , dp[i][j][k][l]+=dp[i-1][j][k][l-1];

3、b[j]==a[k], dp[i][j][k][l]+=dp[i][j-1][k-1][l];

4、b[j]==b[l], dp[i][j][k][l]+=dp[i][j-1][k][l-1];

但是这个四维的方程要TLE啊,怎么办呢?我们想想能不能减少一维的枚举,于是可以发现:因为要保证第一个人和第二个人的输出序列一样,那么取的球的数量一定一样,即可改一下dp数组的定义,dp[i][j][k],l可用i+j-k来表示。

然后我就wa了,为什么呢?

因为空间要爆,大佬告诉我要开滚动,看看ijk都是由-1转移过来的,那么任选一个都可以吧?果断选了k……然而在for循环中,k是最后枚举的,k对应了很多值,mod2之后就重复对应了……

听大佬的建议,我把dp重新定义为了 两个人都取了i个球,第一个人去j个上排,第二个人取k个上排,然后i开滚动

现在想来应该可以不用改dp定义,直接i开滚动也行,因为i是第一个for的,不至于会出事

初值也是挺有讲究的东西

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int N=500+5;
const int mod=1024523; int n,m;
char c[N],d[N],a[N],b[N];
int dp[2][N][N]; int main(){
scanf("%d%d",&n,&m);
scanf("%s%s",c+1,d+1);
for(int i=1;i<=n;i++){
a[n-i+1]=c[i];
}
for(int i=1;i<=m;i++){
b[m-i+1]=d[i];
}
dp[0][0][0]=1;
for(int i=1;i<=n+m;i++){
for(int j=max(0,i-m);j<=min(i,n);j++){
for(int k=max(0,i-m);k<=min(i,n);k++){
dp[i%2][j][k]=0;//在滚啊,上一次的值要清零
if(a[j]==a[k]&&j-1>=0&&k-1>=0) dp[i%2][j][k]=(dp[i%2][j][k]+dp[(i-1)%2][j-1][k-1])%mod;
if(i-k<=m&&a[j]==b[i-k]&&j-1>=0) dp[i%2][j][k]=(dp[i%2][j][k]+dp[(i-1)%2][j-1][k])%mod;
if(i-j<=m&&b[i-j]==a[k]&&k-1>=0) dp[i%2][j][k]=(dp[i%2][j][k]+dp[(i-1)%2][j][k-1])%mod;
if(i-j<=m&&i-k<=m&&b[i-j]==b[i-k]) dp[i%2][j][k]=(dp[i%2][j][k]+dp[(i-1)%2][j][k])%mod;
}
}
}
printf("%d",(dp[(m+n)%2][n][n])%mod);
return 0;
}

总结:

1、灵活的根据某些性质降维

2、开滚动数组的时候要注意开法,不能互相影响

3、如果滚动数组不是直接赋值覆盖的话,需要清零

上一篇:1000行基本SQL


下一篇:centos6下的mysql的安装