【BZOJ 4145】[AMPPZ2014] The Prices

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4145
神犇题解：http://blog.csdn.net/popoqqq/article/details/46547683

解题报告

先来说一个自己YY的暴力
枚举每一个合法集合，考虑这个集合的物品全部在某一个商店购买
如果我们把这些集合再拿来搞一搞组合，显然可以搞出来正确答案
使用背包DP的话，直接做复杂度是$O(4^m)$，考虑一点优化：
根据我们对于集合的定义，两个集合能够组合在一起，当且仅当两个集合没有交集
然后写个程序跑一跑，发现这种组合大概只会有4e7个，于是暴力搞一搞就好啦！
然后就垫底了 QwQ

现在考虑正解
刚刚我们其实是把整个商店买了哪些物品当作一个新物品，然后用新物品来进行背包DP
考虑我们直接把商店里面的物品拿来做背包DP会有什么问题：商店本身的花费$d_i$不好整
于是我们分阶段来背包DP，每一个商店一个阶段。
在这个阶段中，我们给所有状态加上这个商店的花费$d_i$，表示我们钦定这个商店要买东西
然后把物品拿来做背包，最后再和上个阶段的对应状态取个$min$
然后就做完啦！时间复杂度： $O(nm{2^m})$

Code

贴的这份代码是我YY的暴力

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100+9;
const int M = 65536;

int n,m,cost[N],f[M];
pair<int,int> que[M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

void DFS(int w, int sta, int c) {
	if (w == m + 1) {
		f[sta] = min(f[sta], c);
	} else {
		DFS(w+1, sta, c);
		DFS(w+1, sta|(1<<w-1), c+cost[w]);
	}
}

void update(int t, int sta, int w) {
	if (t == m + 1) {
		f[sta|w] = min(f[sta|w], f[sta] + f[w]);
	} else {
		update(t+1, sta, w);
		if ((sta&(1<<(t-1))) == 0)
			update(t+1, sta, w|(1<<(t-1)));
	}
}

int main() {
	memset(f,60,sizeof(f));
	n = read(); m = read();
	for (int i=1,d;i<=n;i++) {
		d = read();
		for (int j=1;j<=m;j++) 
			cost[j] = read();
		DFS(1, 0, d);
	}
	for (int i=1,lim=1<<m;i<lim;i++)
		que[i] = make_pair(__builtin_popcount(i), i);
	sort(que+1, que+(1<<m));
	for (int i=1,lim=1<<m;i<lim;i++) 
		update(1, que[i].second, 0);
	printf("%d\n",f[(1<<m)-1]);
	return 0;
}

—————————— UPD 2017.2.7 ——————————
感觉使用以下代码来枚举子集可能会使我的暴力不那么接近于TLE：

for (int i=s;i;i=(i-1)&s) {}