2018百度之星-调查问卷(状压dp)

题意


Problem Description
度度熊为了完成毕业论文,需要收集一些数据来支撑他的论据,于是设计了一份包含 m 个问题的调查问卷,每个问题只有 ‘A’ 和 ‘B’ 两种选项。 将问卷散发出去之后,度度熊收到了 n 份互不相同的问卷,在整理结果的时候,他发现可以只保留其中的一部分问题,使得这 n 份问卷仍然是互不相同的。这里认为两张问卷是不同的,当且仅当存在至少一个被保留的问题在这两份问卷中的回答不同。 现在度度熊想知道,存在多少个问题集合,使得这 n 份问卷在只保留这个集合的问题之后至少有 k 对问卷是不同的。

Input
第一行包含一个整数 T,表示有 T 组测试数据。 接下来依次描述 T 组测试数据。对于每组测试数据: 第一行包含三个整数 n,m 和 k,含义同题目描述。 接下来 n 行,每行包含一个长度为 m 的只包含 ‘A’ 和 ‘B’ 的字符串,表示这份问卷对每个问题的回答。 保证 1≤T≤100,1≤n≤103,1≤m≤10,1≤k≤106,给定的 n 份问卷互不相同。

Output
对于每组测试数据,输出一行信息 “Case #x: y”(不含引号),其中 x 表示这是第 x 组测试数据,y 表示满足条件的问题集合的个数,行末不要有多余空格。

Sample Input
Copy
2
2 2 1
AA
BB
2 2 2
AA
BBSample Output
Copy
Case #1: 3
Case #2: 0

思路


观察到n比较大,m很小,而且是一个集合问题。所以我们可以想到这里可以利用二进制枚举集合的状态,$2^10 = 1024$。那么剩下的问题就是怎么去验证。dp[i][j]表示前i个物品中当集合状态为j时不同的问卷数目.
注意观察,只要有一位不同就算不同,所以我们开一个数组,num[sta]前面1~i-1个物品中,当集合状态为j时,和i问卷答案相同(i的答案此时为sta)的问卷数,那么剩下的都不同,即有:
dp[i][j] = dp[i - 1][j] + i - num[sta].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e3+5;
int dp[maxn][1025],num[1025];
char str[maxn][12];
int n,m,k;
int main()
{
int _,ca = 1;
cin >> _;
while(_--)
{
scanf("%d%d%d",&n,&m,&k);
for(int i = 1;i <= n;++i)
scanf("%s",str[i]);
memset(dp,0,sizeof dp);
for(int sta = 0;sta < (1 << m);++sta)
{
memset(num,0,sizeof num);
for(int i = 1;i <= n;++i)
{
int tmp = 0;
for(int j = 0;j < m;++j)
if(sta & (1 << j) && str[i][j] == 'A')
tmp |= (1 << j);
num[tmp]++;
dp[i][sta] = dp[i - 1][sta] + i - num[tmp];
}
}
ll ans = 0;
for(int sta = 0;sta < (1 << m);++sta)
if(dp[n][sta] >= k) ans++;
printf("Case #%d: %I64d\n",ca++,ans);
}
return 0;
}

-------------本文结束感谢您的阅读-------------

万水千山总是情,就给五毛行不行!

相关文章: