BZOJ 3163: [Heoi2013]Eden的新背包问题

###Description
“寄没有地址的信，这样的情绪有种距离，你放着谁的歌曲，是怎样的心心静，能不能说给我听。”
失忆的Eden总想努力地回忆起过去，然而总是只能清晰地记得那种思念的感觉，却不能回忆起她的音容笑貌。 记忆中，她总是喜欢给Eden出谜题：在 valentine’s day 的夜晚，两人在闹市中闲逛时，望着礼品店里精巧玲珑的各式玩偶，她突发奇想，问了 Eden这样的一个问题：有n个玩偶，每个玩偶有对应的价值、价钱，每个玩偶都可以被买有限次，在携带的价钱m固定的情况下，如何选择买哪些玩偶以及每个玩偶买多少个，才能使得选择的玩偶总价钱不超过m，且价值和最大。众所周知的，这是一个很经典的多重背包问题，Eden很快解决了，不过她似乎因为自己的问题被飞快解决感到了一丝不高兴，于是她希望把问题加难：多次 询问，每次询问都将给出新的总价钱，并且会去掉某个玩偶（即这个玩偶不能被选择），再问此时的多重背包的答案（即前一段所叙述的问题）。
这下Eden 犯难了，不过Eden不希望自己被难住，你能帮帮他么？

###Input
第一行一个数n，表示有n个玩偶，玩偶从0开始编号
第二行开始后面的 n行，每行三个数 ai, bi, c i，分别表示买一个第i个玩偶需要的价钱，获得的价值以及第i个玩偶的限购次数。
接下来的一行为q，表示询问次数。
接下来q行，每行两个数di. ei表示每个询问去掉的是哪个玩偶（注意玩偶从0开始编号）以及该询问对应的新的总价钱数。（去掉操作不保留，即不同询问互相独立）

###Output
输出q行，第i行输出对于第 i个询问的答案。

###Sample Input
5
2 3 4
1 2 1
4 1 2
2 1 1
3 2 3
5
1 10
2 7
3 4
4 8
0 5

###Sample Output
13
11
6
12
4

###Solution
多重背包+分治背包
递归处理[l,r)，每次加入左半部分的点，处理右边，再加入右边，处理左边
时间复杂度$$O(n^2log^2n+q)$$

###Code
```c++
#include<bits/stdc++.h>

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline void repr(T &a,T b){if(a<b)a=b;}
template<typename T> inline void repl(T &a,T b){if(a>b)a=b;}
template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define lb(x) ((x)&(-(x)))
#define sqr(x) ((x)*(x))
#define pm(a,b,c,d) a=(a+(ll)(b)*(c))%(d)

struct _toy
{
	int a,b,c;
}toy[1000];

struct _qr
{
	int w,ans,ne;
}qr[300001];

int p[1000],n,q,f[11][1001];

inline void merge(int *s,int a,int b)
{
	for(int i=1000;i>=a;i--)
		repr(s[i],max(s[i-1],s[i-a]+b));
}

void solve(int l,int r,int d)
{
	if(l+1==r)
	{
		for(int i=p[l];i;i=qr[i].ne)
			qr[i].ans=f[d][qr[i].w];
	}
	else
	{
		int p=(l+r)>>1;
		memcpy(f[d+1],f[d],sizeof(f[d]));
		for(int i=l;i<p;i++)
		{
			int t=toy[i].c;
			for(int j=1;j<t;t-=j,j<<=1)
				merge(f[d+1],toy[i].a*j,toy[i].b*j);
			merge(f[d+1],toy[i].a*t,toy[i].b*t);
		}
		solve(p,r,d+1);
		memcpy(f[d+1],f[d],sizeof(f[d]));
		for(int i=p;i<r;i++)
		{
			int t=toy[i].c;
			for(int j=1;j<t;t-=j,j<<=1)
				merge(f[d+1],toy[i].a*j,toy[i].b*j);
			merge(f[d+1],toy[i].a*t,toy[i].b*t);
		}
		solve(l,p,d+1);
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d%d%d",&toy[i].a,&toy[i].b,&toy[i].c);
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		int x;
		scanf("%d%d",&x,&qr[i].w);
		qr[i].ne=p[x];
		p[x]=i;
	}
	solve(0,n,0);
	for(int i=1;i<=q;i++)
		printf("%d\n",qr[i].ans);
}
```

BZOJ 3163: [Heoi2013]Eden的新背包问题

最新文章

最近回复

分类

归档

其它