JZOJ 3223. 【HBOI2013】Ede的新背包问题

traveller-ly 2018-08-20 原文

JZOJ 3223. 【HBOI2013】Ede的新背包问题

Description

Input

Output

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

Sample Input

Sample Output

Data Constraint

做法：思考一下假如题目没有去掉某个玩偶，而只是给定q个询问，然后改变m的值，我们会怎么做？

我们会找到最大的m，然后跑一遍多重背包就好了。

　　 然后思考一下当时的转移方程？ f[i] = max(f[i], f[i – vi] + wi); 对吗？我们在学习背包的时候得知，

空间上是可以只用一维的，那么如果我们不去掉那一维呢？f[i][j] = max(f[i][j], f[i – 1][j – vi] + wi)，f[i][j]表示

做完了前i个物品，可以获得的最大价值。显然此时的i其实是没有影响的，所以我们省去，但如果不省去，我们

不就获得了过程中最优吗？看到这是不是想到怎么做了，我们跑两遍，正着来一遍，反着来一遍，然后直接统计

答案就好啦。

代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #define N 2007
 5 #define LL long long
 6 using namespace std;
 7 int n, q, w[N], v[N], c[N];
 8 LL f[N][N], g[N][N];
 9 
10 int max(int a, int b)
11 {
12     if (a > b)    return a;
13     return b;
14 }
15 
16 void Init()
17 {
18     scanf("%d", &n);
19     for (int i = 1; i <= n; i++)
20         scanf("%d%d%d", &v[i], &w[i], &c[i]);
21 }
22 
23 void Dp()
24 {
25     for (int i = 1; i <= n; i++)
26         for (int j = 1000; j >= 0; j--)
27         {
28             f[i][j] = f[i - 1][j];
29                 for (int k = 1; k <= c[i]; k++)
30                     if (j >= k * v[i])    f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
31                     else break;
32         }
33     memset(g, 0, sizeof(g));
34     for (int i = n; i >= 1; i--)
35         for (int j = 1000; j >= 0; j--)
36         {
37             g[i][j] = g[i + 1][j];
38                 for (int k = 1; k <= c[i]; k++)
39                     if (j >= k * v[i])    g[i][j] = max(g[i][j], g[i + 1][j - k * v[i]] + k * w[i]);
40                     else break;
41         }
42 }
43 
44 int main()
45 {
46     Init();
47     Dp();
48     scanf("%d", &q);
49     for (; q--; )
50     {
51         int m, ban;
52         scanf("%d%d", &ban, &m);
53         int ans = 0;
54         for (int i = 0; i <= m; i++)
55                 ans = max(ans, f[ban][m - i] + g[ban + 2][i]);
56         printf("%d\n", ans);
57     }
58 }