UVA1099 Sharing Chocolate

状压dp

3.UVA1099 Sharing Chocolate

题目描述

给出一块长为 xx, 宽为 yy 的矩形巧克力，每次操作可以沿一条直线把一块巧克力切割成两块长宽均为整数的巧克力（一次不能同时切割多块巧克力）。

问：是否可以经过若干次操作得到 nn 块面积分别为 a1,a2,...,ana_1, a_2, ..., a_n 的巧克力

题目分析

因为一次切割只能横着切或者竖着切，同时考虑到nn非常小，那么考 dp[x][y][z]dp[x][y][z] 表示长 xx ，宽 yy 的巧克力能不能分割出状态 ss 的巧克力。状态转移时枚举 ss 的子集。但是这样进行状态转移的时间复杂度为 O(x∗y∗(x+y)∗3n)O(x*y*(x+y)*3^n) 总的状态数有x∗y∗2nx*y*2^n 个，这样必然tle，同时仔细一分析，发现如果一块巧克力能恰好分割为若干块，那么他们的面积和必然是一样的。这样可以忽略非常多的状态。同时，知道xx和ss之后就能求出来yy，所以状态变为了dp[x][s]dp[x][s]。时空复杂度都大幅下降。

代码

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
//
// Created by mrx on 2022/10/28.
//
#include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <cmath>
#include <queue>
#include <array>
#include <map>

using i64 = long long;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	int n;
	int cas = 1;
	while (std::cin >> n && n) {
		int x, y;
		std::cin >> x >> y;
		std::vector<int> a(n);
		for (int i = 0; i < n; ++i)std::cin >> a[i];
		std::vector<int> sum(1 << n);
		for (int s = 0; s < 1 << n; ++s) {
			int tmp = s;
			while (tmp) {
				int lbt = tmp & -tmp;
				int i = __builtin_ctz(lbt);
				sum[s] += a[i];
				tmp -= lbt;
			}
		}

//		std::vector<std::vector<std::vector<bool>>> mp(105, std::vector<std::vector<bool>>(105, std::vector<bool>(1 << n)));
//		std::vector<std::vector<std::vector<bool>>> vis(105, std::vector<std::vector<bool>>(105, std::vector<bool>(1 << n)));
//
//		std::function<bool(int, int, int)> dfs = [&](int c, int r, int s) -> bool {
//			if (vis[c][r][s])return mp[c][r][s];
//			vis[c][r][s] = true;
//
//			if (c == 1) return mp[c][r][s] = r >= sum[s];
//			if (r == 1) return mp[c][r][s] = c >= sum[s];
//
//			for (int s0 = s; s0; s0 = s & (s0 - 1)) {
//				for (int j = 1; j < c; ++j) if (dfs(c - j, r, s0) && dfs(j, r, s ^ s0))return mp[c][r][s] = true;
//				for (int j = 1; j < r; ++j) if (dfs(c, r - j, s0) && dfs(c, j, s ^ s0))return mp[c][r][s] = true;
//			}
//
//			return mp[c][r][s] = false;
//		};

		std::vector<std::vector<bool>> dp(101, std::vector<bool>(1 << n));
		std::vector<std::vector<bool>> vis(101, std::vector<bool>(1 << n));

		std::function<bool(int, int)> dfs = [&dp, &vis, &sum, &dfs](int x, int s) -> bool {
			if (vis[x][s])return dp[x][s];
			vis[x][s] = true;
			if (__builtin_popcount(s) == 1)return dp[x][s] = true;
			int y = sum[s] / x;
			for (int s0 = (s - 1) & s; s0; s0 = (s0 - 1) & s) {
				int x0 = sum[s0] / y;
				int y0 = sum[s0] / x;
				int x1 = sum[s ^ s0] / y;
				int y1 = sum[s ^ s0] / x;
				if (sum[s0] % x == 0 && dfs(std::min(x, y0), s0) && dfs(std::min(x, y1), s0 ^ s))return dp[x][s] = true;
				if (sum[s0] % y == 0 && dfs(std::min(x0, y), s0) && dfs(std::min(x1, y), s ^ s0))return dp[x][s] = true;
			}
			return dp[x][s] = false;
		};

		std::cout << "Case " << cas++ << ": ";
		std::cout << (dfs(std::min(x, y)//
// Created by mrx on 2022/10/28.
//
#include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <cmath>
#include <queue>
#include <array>
#include <map>

using i64 = long long;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	int n;
	int cas = 1;
	while (std::cin >> n && n) {
		int x, y;
		std::cin >> x >> y;
		std::vector<int> a(n);
		for (int i = 0; i < n; ++i)std::cin >> a[i];
		std::vector<int> sum(1 << n);
		for (int s = 0; s < 1 << n; ++s) {
			int tmp = s;
			while (tmp) {
				int lbt = tmp & -tmp;
				int i = __builtin_ctz(lbt);
				sum[s] += a[i];
				tmp -= lbt;
			}
		}

//		std::vector<std::vector<std::vector<bool>>> mp(105, std::vector<std::vector<bool>>(105, std::vector<bool>(1 << n)));
//		std::vector<std::vector<std::vector<bool>>> vis(105, std::vector<std::vector<bool>>(105, std::vector<bool>(1 << n)));
//
//		std::function<bool(int, int, int)> dfs = [&](int c, int r, int s) -> bool {
//			if (vis[c][r][s])return mp[c][r][s];
//			vis[c][r][s] = true;
//
//			if (c == 1) return mp[c][r][s] = r >= sum[s];
//			if (r == 1) return mp[c][r][s] = c >= sum[s];
//
//			for (int s0 = s; s0; s0 = s & (s0 - 1)) {
//				for (int j = 1; j < c; ++j) if (dfs(c - j, r, s0) && dfs(j, r, s ^ s0))return mp[c][r][s] = true;
//				for (int j = 1; j < r; ++j) if (dfs(c, r - j, s0) && dfs(c, j, s ^ s0))return mp[c][r][s] = true;
//			}
//
//			return mp[c][r][s] = false;
//		};

		std::vector<std::vector<bool>> dp(101, std::vector<bool>(1 << n));
		std::vector<std::vector<bool>> vis(101, std::vector<bool>(1 << n));

		std::function<bool(int, int)> dfs = [&dp, &vis, &sum, &dfs](int x, int s) -> bool {
			if (vis[x][s])return dp[x][s];
			vis[x][s] = true;
			if (__builtin_popcount(s) == 1)return dp[x][s] = true;
			int y = sum[s] / x;
			for (int s0 = (s - 1) & s; s0; s0 = (s0 - 1) & s) {
				int x0 = sum[s0] / y;
				int y0 = sum[s0] / x;
				int x1 = sum[s ^ s0] / y;
				int y1 = sum[s ^ s0] / x;
				if (sum[s0] % x == 0 && dfs(std::min(x, y0), s0) && dfs(std::min(x, y1), s0 ^ s))return dp[x][s] = true;
				if (sum[s0] % y == 0 && dfs(std::min(x0, y), s0) && dfs(std::min(x1, y), s ^ s0))return dp[x][s] = true;
			}
			return dp[x][s] = false;
		};

		std::cout << "Case " << cas++ << ": ";
		if (sum[(1 << n) - 1] != x * y)std::cout << "No\n";
		else std::cout << (dfs(std::min(x, y), (1 << n) - 1) ? "Yes" : "No") << '\n';
	}
	return 0;
}, (1 << n) - 1) ? "Yes" : "No");
		std::cout << '\n';
	}

	return 0;
}
acm > dp > 状压dp
#dp #状态压缩
UVA1099 Sharing Chocolate
https://mrxyan6.github.io/2022/10/28/UVA1099/
作者
mrx
发布于
2022年10月28日
许可协议