Tag: 背包DP

相关链接

题目传送门：http://codeforces.com/contest/797/problem/F

解题报告

这题我是用的一个非常鬼畜的背包DP过的，时间复杂度：$O(n^2 \log n)$
看提交记录的话，似乎可以用很多种方法做到$O(n^2)$

Code

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

const int N = 5009;
const LL INF = 1e15;

int n,m,sum,x[N];
LL f[N],tmp,cost[N];
pair<int,int> mdy[N];

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;
}

int main() {
	n = read(); m = read();
	for (int i=1;i<=n;i++) x[i] = read(), f[i] = INF;
	for (int i=1;i<=m;i++) mdy[i].first = read(), sum += (mdy[i].second = read());
	if (sum < n) puts("-1"), exit(0);
	sort(x+1, x+1+n); sort(mdy+1, mdy+1+m);
	for (int j=1,tot,pos;tot=mdy[j].second,pos=mdy[j].first,j<=m;j++) {
		for (int i=1;i<=n;i++) cost[i] = abs(x[i] - pos) + cost[i-1];
		for (int len=1;len=min(len,tot),tot>0;tot-=len,len<<=1) {
			for (int l=n-len+1,r=n;l>0;--l,--r) {
				f[r] = min(f[r], cost[r] - cost[l-1] + f[l-1]);
			} 
		}
	}
	printf("%lld\n",f[n]);
	return 0;
}

相关链接

题目传送门：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) {}

链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2794
数据生成器：http://paste.ubuntu.com/23946550/
神犇题解：http://trinklee.blog.163.com/blog/static/23815806020149855817630

题解

这个题目假如没有A[]和B[]的限制的话，就是一个正常的背包
然而有了这两个东西，而且复杂度要求O(1)询问，这样我就不会了 QwQ

考虑传统背包的局限性：
1）添加物品的顺序没有限制，但实际上是浪费了一些性质
2）DP的是一个bool数组，只记录是否可以凑出，这样实际上也是浪费了信息

于是考虑离线，将询问的m和物品的a[]都按照升序排好序
然后规定f[i][j]表示用前i个物品，凑出j的b[]的最小值的最大值
之后对于每个询问，A[]可以用i来限制，B[]可以直接判断

于是边DP边回答询问的话
就可以O(1)处理所有询问辣！
★,°:.☆(￣▽￣)/$:.°★ 。

Code

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

const int N = 1000+9;
const int M = 1000000+9;
const int INF = 100000;

struct Event{
	int a,b,c,d;
	inline Event() {}
	inline Event(int _a, int _b, int _c):a(_a),b(_b),c(_c) {}
	inline bool operator < (const Event &B) const {return a < B.a;}
}t[N],q[M];

int f[M],arr[M+N<<1],vout[M],tot,n,m,mx;

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;
}

int main() {
	n = read();
	for (int i=1,a,b,c;i<=n;i++) {
		a = read(); b = read(); c = read();
		arr[++tot] = c; arr[++tot] = b;
		t[i] = Event(b, c, a);
	}
	m = read();
	for (int i=1,a,b,c;i<=m;i++) {
		a = read(); b = read(); c = read() + a;
		arr[++tot] = a; arr[++tot] = c;
		q[i] = Event(a, c, b);
		q[i].d = i;
	}
	sort(arr+1, arr+1+tot);
	tot = unique(arr+1, arr+1+tot) - arr - 1;
	for (int i=1;i<=n;i++) {
		t[i].a = lower_bound(arr+1, arr+1+tot, t[i].a) - arr;
		t[i].b = lower_bound(arr+1, arr+1+tot, t[i].b) - arr;
		mx = max(mx, t[i].a);
	}
	for (int i=1;i<=m;i++) {
		q[i].a = lower_bound(arr+1, arr+1+tot, q[i].a) - arr;
		q[i].b = lower_bound(arr+1, arr+1+tot, q[i].b) - arr;
		q[i].a = min(q[i].a, mx);
	}
	sort(t+1, t+1+n);
	sort(q+1, q+1+m);
	f[0] = 1e9;
	for (int j=1,p1=1;j<=m;j++) {
		for (;t[p1].a<=q[j].a&&p1<=n;p1++) {
			for (int i=INF-t[p1].c,to=INF;i>=0;i--,to--) {
				f[to] = max(f[to], min(f[i], t[p1].b));	
			}
		}
		vout[q[j].d] = f[q[j].c] > q[j].b;
	}
	for (int i=1;i<=m;i++) {
		if (vout[i]) puts("TAK");
		else puts("NIE");
	}
	return 0;
}