BZOJ1879 [Sdoi2009]Bill的挑战【状压dp】

题目

输入格式

本题包含多组数据。

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

对于每组数据：

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

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

T ≤ 5，M ≤ 15，字符串长度≤ 50。

输出格式

如题

输入样例

3 3

???r???

???????

3 4

???????

?????a?

???????

3 3

???????

?a??j??

????aa?

3 2

a??????

???????

3 2

???????

???a???

????a??

输出样例

914852

871234

67018

题解

如此简单的状压为啥我想不到QAQ

设\(f[i][s]\)表示前\(i\)位匹配状态为\(s\)的方案数

枚举\(i + 1\)位的字符，更新状态即可

最后统计一下答案

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");

using namespace std;

const int maxn = 20,maxm = 55,INF = 1000000000,P = 1000003;

char S[maxn][maxm];

int N,K,T,len;

LL f[maxm][1 << 15];

int main(){

	cin >> T;

	while (T--){

		cin >> N >> K;

		for (int i = 1; i <= N; i++) scanf("%s",S[i] + 1);

		len = strlen(S[1] + 1);

		int maxv = (1 << N) - 1;

		for (int i = 0; i <= len; i++)

			for (int s = 0; s <= maxv; s++)

				f[i][s] = 0;

		f[0][maxv] = 1;

		for (int i = 0; i < len; i++){

			for (int s = 0; s <= maxv; s++){

				if (!f[i][s]) continue;

				for (char c = 'a'; c <= 'z'; c++){

					int e = 0;

					for (int j = 1; j <= N; j++)

						if (S[j][i + 1] == '?' || S[j][i + 1] == c)

							e |= (1 << j - 1);

					f[i + 1][s & e] = (f[i + 1][s & e] + f[i][s]) % P;

				}

			}

		}

		LL ans = 0;

		for (int s = 0; s <= maxv; s++){

			int cnt = 0,e = s;

			while (e) cnt += (e & 1),e >>= 1;

			if (cnt == K) ans = (ans + f[len][s]) % P;

		}

		cout << ans << endl;

	}

	return 0;

}

巴特西

BZOJ1879 [Sdoi2009]Bill的挑战【状压dp】

题目

输入格式

输出格式

输入样例

输出样例

题解

最新文章

热门文章

巴特西

BZOJ1879 [Sdoi2009]Bill的挑战 【状压dp】

题目

输入格式

输出格式

输入样例

输出样例

题解

最新文章

热门文章

BZOJ1879 [Sdoi2009]Bill的挑战【状压dp】