Greetings（状压DP，枚举子集转移）

https://codeforces.com/gym/101002

题意
一共 n 种信件，每种信件有属性 $w_i,h_i,c_i$ 分别表示 长，宽 和 个数。
现在有 k 次设计信封的机会，每种信封也有长和宽，仅当信封的长和宽都分别大于等于信件的长和宽时，信件才能放到信封中，放置方向固定。
如果信件尺寸为 $w$ 和 $h$，信封尺寸为 $W$ 和 $H$ $(w\le W,h\le H)$，那么浪费的面积为 $W\ast H-w\ast h$。
要设计出最多 k 种信封将 n 种信件都放进去。
问，如何设计信封能够使得浪费的总面积最小？ 输出最小浪费总面积。

$(1\le n,k\le 15,1\le w_i,h_i,c_i\le 10,000)$

思路
n 很小，考虑两种算法：二进制枚举 和 状压DP。

首先考虑二进制枚举：
所有的信件都要被放到信封里，k 次机会，枚举啥，没啥可枚举的，作罢。

然后考虑状压DP：
因为多了 k 次机会这样变量，所以多定义一维状态。
定义状态 f[i, j] 表示，用了 i 种信封，装下状态为 j 的所有信件，所浪费的最小总面积。

状态转移：
用了 i 种信封可以从 用了 i-1 种信封的状态来转移，而对于一种信封，可能会装多种信件，所以集合也要用集合来更新。
对于状态 f[i, j] 来说，枚举集合 j 的子集 k，将其作为用第 i 种信封装的信件，那么前 i-1 种信封装的信件构成的集合就为该集合其余元素 j^k。
用前i-1种信封装的信件构成的集合 加上 第i种信封装的信件构成的集合 来更新 前i种信封装的信件构成的集合，即，用 f[i-1, j^k] 加上 该集合的花费 cost[k] 来更新 f[i, j]。
即，f[i, j] = f[i-1, k] + cost[j ^ k]。

然后问题就在于，如何枚举集合 i 的子集？
如果是重新遍历所有二进制数判断是否是子集的话，时间复杂度为 $O(n^{2n})$。

下面来看一个复杂度较低的做法：
对于初始化子集 j 为集合 i，然后 j 不断 -1，结果和集合 i 取与，保证其为子集。

for(int i = 0; i < 1<<n; i++)
	for(int j = i; j > 0; j = (j-1)&i)
		...							 //此时 j 即为 i 的子集
1
2
3

时间复杂度：$O(n^3)$，证明。

所以转移过程即为：

for(int i=1;i<=m;i++) //遍历使用的信封数
{
	for(int j=0;j<1<<n;j++) //遍历用了i种信封所装的信件状态
	{
		for(int k = j; k > 0; k = (k-1) & j) //遍历j的子集k作为用第i种信封装的信件状态，用以更新f[i, j]。
		{
			f[i][j] = min(f[i][j], f[i-1][j^k] + cost[k]);
		}
	}
}
1
2
3
4
5
6
7
8
9
10

当然，也可以把枚举的子集k作为前 i-1 种信封所装的信件状态，那么状态转移方程即为：f[i, j] = min(f[i, j], f[i-1, k] + cost[j^k]。
但是这样写放到上面的代码里得不出答案，因为遍历子集的操作不会遍历到空集合，也就是 k 不会为 0，那么就始终不会从 f[0, 0] 来转移，状态一直不会被更新。而如果因此第三重遍历改为 k>=0 的话，当 k=0 时，下一个 k = (k-1) & j 继续执行，此重循环将会一直执行。所以需要在 k=0 将此重循环手动停止掉，代码修改为：

for(int i=1;i<=m;i++)
{
	for(int j=0;j<1<<n;j++)
	{
		for(int k = j; k >= 0; k = (k-1) & j) //此时的k作为j的子集表示的是，前i-1种信封装的信件状态，j^k表示的是第i种信封装的信件状态，用这两个来更新前i种信封。
		{
			f[i][j] = min(f[i][j], f[i-1][k] + cost[j^k]);
			if(k == 0) break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11

相较而言，第一种转移方式更简洁。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int f[16][1<<15];
struct node{
	int w, h, cnt;
}a[N];
int cost[1<<15];

void pre()
{
	for(int i=0;i<1<<n;i++) //预处理出，针对每一个集合所设计的信封得到的最小消耗值
	{
		int maxw = 0, maxh = 0;
		for(int j=0;j<n;j++)
		{
			if(!(i >> j & 1)) continue;
			maxw = max(maxw, a[j].w);
			maxh = max(maxh, a[j].h);
		}
		for(int j=0;j<n;j++)
		{
			if(!(i >> j & 1)) continue;
			cost[i] += a[j].cnt * (maxw*maxh - a[j].w*a[j].h);
		}
	}
	
	for(int i=0;i<=m;i++) //状态初始为正无穷
		for(int j=0;j<1<<n;j++)
			f[i][j] = 1e18;
	f[0][0] = 0;
}

signed main(){
	Ios;
	cin >> n >> m;
	
	m = min(n, m); //如果信封种类大于信件个数的话，需要取个min，否则后面转移不过来。
	
	for(int i=0;i<n;i++)
		cin >> a[i].w >> a[i].h >> a[i].cnt;
	
	pre();
	
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<1<<n;j++)
		{
//			f[i][j] = min(f[i][j], f[i-1][j]); //要不然就继承上一个状态，一直取最小 
			for(int k = j; k > 0; k = (k-1) & j)
			{
				f[i][j] = min(f[i][j], f[i-1][j^k] + cost[k]);
			}
//			for(int k = j; k >= 0; k = (k-1) & j)
//			{
//				f[i][j] = min(f[i][j], f[i-1][k] + cost[j^k]);
//				if(k == 0) break;
//			}
		}
	}
	cout << f[m][(1<<n) - 1];
	
	return 0;
}
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

---

经验
还是第一次遇见用集合来更新集合的题目。