[pixiv] https://www.pixiv.net/member_illust.php?mode=medium&illust_id=61891436
向大(hei)佬(e)*学(di)习(tou)
Description
Input第一行包含两个整数n, m,分别表示上下两个管道中球的数目。 第二行为一个AB字符串,长度为n,表示上管道中从左到右球的类型。其中A表示浅色球,B表示深色球。 第三行为一个AB字符串,长度为m,表示下管道中的情形。
Output仅包含一行,即为 Sigma(Ai^2) i从1到k 除以1024523的余数。
Sample Input2 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、如果滚动数组不是直接赋值覆盖的话,需要清零