hdu 5119 Happy Matt Friends 01背包方案计数

缘起

【1】研究了01背包最优解方案计数问题. 本题来研究未必最优解, 但是满足一定条件的01背包方案计数问题. hdu 5119 Happy Matt Friends

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
有n个数，问有多少方案满足取几个数的异或值>=m;

【输入】
多样例, 第一行是样例数. 对每个样例, 第一行是n和m
1 ≤ N ≤ 40, 0 ≤ M ≤ 10^6
第二行是n个数, 数的范围是[0,10^6]

【输出】
输出多少种方案. 具体输出格式见样例

【样例输入】
2
3 2
1 2 3
3 3
1 2 3

【样例输出】
Case #1: 4
Case #2: 2

【限制】
6s

显然是01背包的变形

1
2
3
4
5
6
7
8
令 dp[i][j]是仅仅考虑前i个数a[1,..,i], xor结果=j的方案数. 则
dp[i][j] 根据选不选第i个数分类讨论
dp[i][j] = dp[i-1][j]+dp[i-1][j^a[i]] （注意, xor具备 a^a=0的性质,所以x^a[i]=j, 则两边再xor
上a[i]就得到了x=j^a[i]）
初始值是 dp[0][0] = 1,dp[0][j] = 0, 1<=j<=m
滚动一下数组就是
dp[j] += dp[j^a[i]]
dp[0] =1, dp[j] = 0, 1<=j<=m

遂写下如下代码, 其中maxv=1<<20是因为100w是20比特位, 最大全部为1, 那就是1<<20≈104万~

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
39
40
41
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL
const int maxn = 45, maxv = (1<<20);
int n,m, a[50], dp[2][maxv];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	for (int kse = 1,k;kse<=kase;kse++)
	{
		scanf("%d%d", &n,&m);
		for (int i = 1;i<=n; i++)
		{
			scanf("%d", a+i);
		}
		memset(dp,0,sizeof(dp));
		dp[k=0][0] = 1; // dp初始化
		for (int i = 1;i<=n;i++)
		{
			k = 1-k;
			for (int j = 0;j<maxv;j++)
			{
				dp[k][j] = dp[1-k][j] + dp[1-k][j^a[i]];
			}
		}
		long long ans = 0;
		for (int i = m;i<maxv; i++)
		{
			ans+=dp[k][i];
		}
		printf("Case #%d: %lld\n", kse, ans);
	}
	return 0;
}

注意, 上面用了滚动数组, 为什么? 因为这里不是传统意义上的01背包, 即大的v会用到小的v进行dp, 这里是v用到 v^a[i]的结果进行dp. 所以我们仅仅需要保存上层结果就行了（即本层结果, 亦即引入物品i的结果仅仅依赖上一层结果而已。） 所以我们只需要保存2层. 所以dp数组的第一维度为2

ac情况

Status Accepted
Time 483ms
Memory 9948kB
Length 724
Lang C++
Submitted 2019-10-27 15:51:43
Shared
RemoteRunId 31133940

参考

【1】https://yfsyfs.github.io/2019/10/27/hdu-2126-Buy-the-souvenirs-01%E8%83%8C%E5%8C%85%E6%B1%82%E6%9C%80%E4%BC%98%E6%96%B9%E6%A1%88%E6%95%B0/