Schrödinger's Knapsack(DP乱搞)

描述

传送门:The 18th Zhejiang University Programming Contest Sponsored by TuSimple - Problem F

DreamGrid has a magical knapsack with a size capacity of $c$ called the Schrödinger’s knapsack (or S-knapsack for short) and two types of magical items called the Schrödinger’s items (or S-items for short). There are $n$ S-items of the first type in total, and they all have a value factor of $k_1$; While there are $m$ S-items of the second type in total, and they all have a value factor of $k_2$. The size of an S-item is given and is certain. For the $i$-th S-item of the first type, we denote its size by $s_{1,i}$; For the -th S-item of the second type, we denote its size by $s_{2,i}$.

But the value of an S-item remains uncertain until it is put into the S-knapsack (just like Schrödinger’s cat whose state is uncertain until one opens the box). Its value is calculated by two factors: its value factor $k$, and the remaining size capacity $r$ of the S-knapsack just after it is put into the S-knapsack. Knowing these two factors, the value of an S-item can be calculated by the formula $v=kr$.

For a normal knapsack problem, the order to put items into the knapsack does not matter, but this is not true for our Schrödinger’s knapsack problem. Consider an S-knapsack with a size capacity of 5, an S-item with a value factor of 1 and a size of 2, and another S-item with a value factor of 2 and a size of 1. If we put the first S-item into the S-knapsack first and then put the second S-item, the total value of the S-items in the S-knapsack is $1 \times (5-2) + 2 \times (3-1) = 7$; But if we put the second S-item into the S-knapsack first, the total value will be changed to $2 \times (5-1) + 1 \times (4-2) = 10$. The order does matter in this case!

Given the size of DreamGrid’s S-knapsack, the value factor of two types of S-items and the size of each S-item, please help DreamGrid determine a proper subset of S-items and a proper order to put these S-items into the S-knapsack, so that the total value of the S-items in the S-knapsack is maximized.

Input

The first line of the input contains an integer $T$ (about 500), indicating the number of test cases. For each test case:

The first line contains three integers $k_1$, $k2$ and $c$ ($1 \le k_1, k_2, c \le 10^7$), indicating the value factor of the first type of S-items, the value factor of the second type of S-items, and the size capacity of the S-knapsack.

The second line contains two integers $n$ and $m$ ($1 \le n, m \le 2000$), indicating the number of the first type of S-items, and the number of the second type of S-items.

The next line contains $n$ integers $s_{1,1}, s_{1,2}, \dots, s_{1,n}$ ($1 \le s_{1,i} \le 10^7$), indicating the size of the S-items of the first type.

The next line contains $m$ integers $s_{2,1}, s_{2,2}, \dots, s_{2,m}$ ($1 \le s_{2,i} \le 10^7$), indicating the size of the S-items of the second type.

It’s guaranteed that there are at most 10 test cases with their $\max(n, m)$ larger than 100.

Output

For each test case output one line containing one integer, indicating the maximum possible total value of the S-items in the S-knapsack.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
3
3 2 7
2 3
4 3
1 3 2
1 2 10
3 4
2 1 2
3 2 3 1
1 2 5
1 1
2
1

Sample Output

1
2
3
23
45
10

Hint

For the first sample test case, you can first choose the 1st S-item of the second type, then choose the 3rd S-item of the second type, and finally choose the 2nd S-item of the first type. The total value is $2 \times (7-1) + 2 \times (6-2) + 3 \times (4-3) = 23$.

For the second sample test case, you can first choose the 4th S-item of the second type, then choose the 2nd S-item of the first type, then choose the 2nd S-item of the second type, then choose the 1st S-item of the second type, and finally choose the 1st S-item of the first type. The total value is $2 \times (10-1) + 1 \times (9-1) + 2 \times (8-2) + 2 \times (6-3) + 1 \times (3-2) = 45$.

The third sample test case is explained in the description.

It’s easy to prove that no larger total value can be achieved for the sample test cases.

思路

  • 首先通过手玩样例,我们可以发现一个比较显然的贪心:同组物品一定先取体积小的。(显然小的物品先取只会使答案更优)
  • 那么两组物品,直接DP就好。令$dp[i][j]$表示第一种物品取$i$件,第二种物品取$j$件的最大价值。
    状态转移:
    $$dp[i][j] = \max(dp[i-1][j]+k_1(\sum_{k=0}^i s_{1,k} + \sum_{k=0}^j s_{2,k}), dp[i][j-1]+k_2(\sum_{k=0}^i s_{1,k} + \sum_{k=0}^j s_{2,k}))$$
  • 其实就是个暴力转移,注意把转移的条件写清楚就好。求和可以前缀和优化没啥说的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int N = 1 << 11;
int s1[N], s2[N];
ll dp[N][N];
ll sa[N], sb[N];

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int T;
scanf("%d", &T);
while (T--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", s1 + i);
for (int i = 1; i <= m; i++) scanf("%d", s2 + i);
sort(s1 + 1, s1 + n + 1);
sort(s2 + 1, s2 + m + 1);
dp[0][0] = 0;
sa[0] = sb[0] = 0;
ll ans = 0;
for (int i = 1; i <= n; i++)
{
sa[i] = sa[i - 1] + s1[i];
dp[i][0] = dp[i - 1][0] + (c - sa[i]) * a;
if (sa[i] <= c) ans = max(ans, dp[i][0]);
}
for (int i = 1; i <= m; i++)
{
sb[i] = sb[i - 1] + s2[i];
dp[0][i] = dp[0][i - 1] + (c - sb[i]) * b;
if (sb[i] <= c) ans = max(ans, dp[0][i]);
}
for (int i = 1; i <= n && sa[i] <= c; i++)
{
for (int j = 1; j <= m && sa[i] + sb[j] <= c; j++)
{
ll cur = c - sa[i] - sb[j];
dp[i][j] = max(dp[i - 1][j] + cur * a, dp[i][j - 1] + cur * b);
ans = max(ans, dp[i][j]);
}
}
printf("%lld\n", ans);
}
return 0;
}
捐助作者
0%