状压DP之Bill的挑战

题目

P2167 [SDOI2009]Bill的挑战

Sheng bill不仅有惊人的心算能力，还可以轻松地完成各种统计。在昨天的比赛中，你凭借优秀的程序与他打成了平局，这导致Sheng bill极度的不满。于是他再次挑战你。这次你可不能输！(一个不服输让我这个ruoji码了俩小时)

这次，比赛规则是这样的：

给N个长度相同的字符串（由小写英文字母和‘?’组成），\(S_1,S_2,S_3......S_N\),求与这N个串中的刚好K个串匹配的字符串T的个数（答案模1000003）。

若字符串\(S_x\)（1≤x≤N）和T匹配，满足以下条件：

1.\(S_x.length = T.length\)。

2.对于任意的\(1≤i≤S_x.length\)，满足\(S_x[i]='?'\)或者\(s_x[i]=T[i]\)。

其中T只包含小写英文字母。

输入格式

本题包含多组数据。

第一行：一个整数T，表示数据的个数。

对于每组数据：

第一行：两个整数，N和K（含义如题目表述）。

接下来N行：每行一个字符串。

\(T ≤ 5，N ≤ 15\)，字符串长度≤ 50。

输出格式

对于每组数据，输出方案数目（共T行）

样例

样例输入

5

3 3

???r???

???????

???????

3 4

???????

?????a?

???????

3 3

???????

?a??j??

????aa?

3 2

a??????

???????

???????

3 2

???????

???a???

????a??

样例输出

思路

这道题是真的难想，一开始我觉得应该从行数开始枚举进行装压DP，但是看到字符串长度最大为\(50\)，还是算了（汗），容易爆掉，所以转换思想，枚举位数，维护数组\(g[i][j]\)表示第\(i\)个位数下放\(j\)的情况下该列的匹配情况，预处理好像就这些（汗）;
接下来就是紧张刺激的DP环节了，我们定义\(f[i][j]\)为\(T\)串已经匹配了\(i\)位，且与\(n\)个字符串是否匹配的集合为\(j\)，状态边界为\(lim\)，\(f[0][lim-1]=1\),首先枚举位数，然后枚举状态，如果\(f[i][j]==0\)不需要进行操作，可以剪枝，然后枚举字符，在下一状态下添加字符的种类数为本状态加上下一状态的原种类数
最后枚举不同状态，记录该状态与原数组的匹配情况，判断该状态是否包括某一行的位数（即该行匹配），如果是则\(tot++\)，如果\(tot=m\)，叠加\(f[len][当前状态]\)，求解\(ans\)。

代码

#include<bits/stdc++.h>

using namespace std;

const int mod=1e6+3;

const int maxn=100010;

int f[50+5][1<<15],g[50+5][30];

char s[16][50+5];

int T,n,m;

int main(){

	scanf("%d",&T);

	while(T--){

		memset(f,0,sizeof(f));

		memset(g,0,sizeof(g));

		scanf("%d%d",&n,&m);

		for(int i=0;i<n;i++)scanf("%s",s[i]);

		int len=strlen(s[0]);

		for(int i=0;i<len;i++){//枚举位数

			for(int j=0;j<26;j++){//枚举字符

				for(int k=0;k<n;k++){//枚举行数

					if(s[k][i]=='?' || s[k][i]==j+'a')g[i][j]|=(1<<k);//位数为i时j字符的匹配情况

				}

			}

		}

		int lim=(1<<n);

		f[0][lim-1]=1;

		for(int i=0;i<len;i++){//枚举位数

			for(int j=0;j<lim;j++){//枚举状态

				if(f[i][j])//剪枝

					for(int k=0;k<26;k++){//枚举字符

						f[i+1][j&g[i][k]]=(f[i+1][j&g[i][k]]+f[i][j])%mod;

					}

			}

		}

		int ans=0;

		for(int i=0;i<lim;i++){//枚举状态

			int tot=0;

			for(int j=0;j<n;j++){

				if(i & (1<<j))tot++;

			}

			if(tot==m)ans=(ans+f[len][i])%mod;

		}

		printf("%d\n",ans);

	}

}

巴特西

状压DP之Bill的挑战

题目

输入格式

输出格式

样例

样例输入

样例输出

思路

代码

最新文章

热门文章