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

从左到右, 从右到左分别dp一次, 然后就可以回答询问了.

----------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

const int V = 1000;

const int maxn = 1009;

int L[maxn][maxn], R[maxn][maxn];

int w[maxn], v[maxn], c[maxn], N;

int main() {

cin >> N;

for(int i = 1; i <= N; i++)

   scanf("%d%d%d", v + i, w + i, c + i);

memset(L, 0, sizeof L);

for(int i = 1; i <= N; i++) {

memcpy(L[i], L[i - 1], sizeof L[i]);

if(v[i] * c[i] >= V) {

for(int j = v[i]; j <= V; j++)

   L[i][j] = max(L[i][j], L[i][j - v[i]] + w[i]);

} else {

int t = c[i];

for(int k = 1; k <= t; k <<= 1) {

for(int j = V; j >= k * v[i]; j--)

   L[i][j] = max(L[i][j], L[i][j - k * v[i]] + k * w[i]);

t -= k;

}

if(t) {

for(int j = V; j >= t * v[i]; j--)

   L[i][j] = max(L[i][j], L[i][j - t * v[i]] + t * w[i]);

}

}

}

memset(R, 0, sizeof R);

for(int i = N; i; i--) {

memcpy(R[i], R[i + 1], sizeof R[i]);

if(v[i] * c[i] >= V) {

for(int j = v[i]; j <= V; j++)

   R[i][j] = max(R[i][j], R[i][j - v[i]] + w[i]);

} else {

int t = c[i];

for(int k = 1; k <= t; k <<= 1) {

for(int j = V; j >= k * v[i]; j--)

   R[i][j] = max(R[i][j], R[i][j - k * v[i]] + k * w[i]);

t -= k;

}

if(t) {

for(int j = V; j >= t * v[i]; j--)

   R[i][j] = max(R[i][j], R[i][j - t * v[i]] + t * w[i]);

}

}

}

int Q; scanf("%d", &Q);

while(Q--) {

int num, _V, ans = 0;

scanf("%d%d", &num, &_V); num++;

for(int i = 0; i <= _V; i++)

   ans = max(ans, L[num - 1][i] + R[num + 1][_V - i]);

printf("%d\n", ans);

}

return 0;

}

----------------------------------------------------------

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

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 223  Solved: 154
[Submit][Status][Discuss]

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

HINT

一共五种玩偶，分别的价钱价值和限购次数为 (2,3,4)， (1,2,1)， (4,1,2)， (2,1,1)，(3,2,3)。五个询问，以第一个询问为例。第一个询问表示的是去掉编号为1的玩偶，且拥有的钱数为10时可以获得的最大价值，则此时剩余玩偶为(2,3,4)，(4,1,2)，(2,1,1)，(3,2,3)，若把编号为0的玩偶买4个（即全买了），然后编号为3的玩偶买一个，则刚好把10元全部花完，且总价值为13。可以证明没有更优的方案了。注意买某种玩偶不一定要买光。

100. 数据满足1 ≤ n ≤ 1000, 1 ≤ q ≤ 3*105 , 1 ≤  a

i、bi、c i ≤ 100, 0 ≤ d i < n,  0  ≤ei ≤ 1000。

Source