【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;

}