【BZOJ1566】【NOI2009】管道取珠(动态规划)

题面

BZOJ

题解

蛤?只有两档部分分。一脸不爽.jpg

第一档?爆搜,这么显然,爆搜+状压最后统计一下就好了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
#define MOD 1024523
#define MAX 555
int a[1<<24];
int n,m,ans;
char S1[MAX],S2[MAX];
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
void dfs(int n,int m,int S)
{
if(!n&&!m){a[S]++;return;}
if(n)dfs(n-1,m,(S<<1)|(S1[n]-'A'));
if(m)dfs(n,m-1,(S<<1)|(S2[m]-'A'));
}
int main()
{
scanf("%d%d",&n,&m);
scanf("%s",S1+1);scanf("%s",S2+1);
dfs(n,m,0);
for(int i=0;i<1<<24;++i)add(ans,1ll*a[i]*a[i]%MOD);
printf("%d\n",ans);
return 0;
}

这种神仙题思维太优秀了。

考虑一下贡献是什么\(\sum a^2\)

可以理解为两个游戏同时进行,并且状态相同的方案总数

这样就可以\(dp\)了

设\(f[i][j][k][l]\)表示第一个游戏上下面还剩\(i,j\)个珠子,第二个还剩\(k,l\)的方案数

每次转移的时候强制选一样的分别减一就行了

发现\(i+j=k+l\),所以状态只要\(3\)维

洛谷卡空间,再把第一维滚掉就好了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define MOD 1024523
#define MAX 505
int n,m,ans;
char S1[MAX],S2[MAX];
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
int f[2][MAX][MAX];
int main()
{
scanf("%d%d",&n,&m);
scanf("%s",S1+1);scanf("%s",S2+1);
f[n&1][m][n]=1;
for(int i=n,nw=n&1,pw=nw^1;~i;--i,nw^=1,pw^=1)
{
memset(f[pw],0,sizeof(f[pw]));
for(int j=m;~j;--j)
for(int k=n,l;~k;--k)
{
l=i+j-k;if(l<0||l>m)continue;
if(i&&k&&S1[i]==S1[k])add(f[pw][j][k-1],f[nw][j][k]);
if(i&&l&&S1[i]==S2[l])add(f[pw][j][k],f[nw][j][k]);
if(j&&k&&S2[j]==S1[k])add(f[nw][j-1][k-1],f[nw][j][k]);
if(j&&l&&S2[j]==S2[l])add(f[nw][j-1][k],f[nw][j][k]);
}
}
printf("%d\n",f[0][0][0]);
return 0;
}
05-06 17:53