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
|
1. 转移边界。本身边界在 $f_{0,0}$ 位置，表示 没有物品没有花费 的情况，应该初始化为 $0$，但现在平移了 $mov$，所以 $f_{0,mov}=0$。
2. 循环条件。现在把 $mov$ 看成零，因为 $cost$ $value$ $w$ $m$ 都有可能是负值，所以我们必须考虑很小到很大的值。在转移中有 $j-cost_i$ 这一步，所以 $j>=cost_i$ 这是起码的。$j$ 的最大值就是当 $m==2500$ 的时候可以取到 $(mov<<1)+1$ 的值。所以调的最久的
```for(int j=cost[i];j<=(mov<<1)+1;++j)```
已经考虑完毕了。
3. 初始化以及输出。状态转移中使用了 $\max(f_{1,j},...$ ，所以 $f_{i,j}$ 必须初始化为一个极小值，个人喜欢
```const ll INF = 0x3f3f3f3f3f3f3f3f``` ,
但其实不开 *龙龙* 用 `int` 都没有关系。输出的时候我们要找的是所有花费为 $m+mov$ 的情况中收益最高的，所以用 `ans=-INF` 然后遍历即可。
那么本篇题解就...
**还没完呢！小子！**
在循环条件中有一个必不可少的句子：`if(f[k][j-cost[i]]!=-INF)`
为什么？因为他此时依靠的$f_{k,j-cost_i}$ 必须是有意义的。他可能后来被 $f_{0,mov}$ 间接地赋上有意义的值，但是此时他的 ```-INF``` 并不是可以利用的，所以要排除掉。（本蒟蒻在这里 WA了两三次 ... ）
顺带提一下，虽然用 vector 又慢又要手动处理边界，但是 vector 提供的 .at(i) 数组访问形式，在功能上和 [i] 一致，并且在数组越界的时候可以抛出异常，在 Run Time Error 的时候值得一试。
```c++
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mov = 2501;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
vector<ll> cost, value;
vector<vector<ll>> w, f;
void in() {
scanf("%lld%lld", &n, &m);
cost.resize(n + 1), value.resize(n + 1);
w.resize(n + 1, vector<ll>(n + 1));
f.resize(n + 1, vector<ll>(mov * 2 + 5000, -INF));
for (int i = 1; i <= n; ++i)
scanf("%lld%lld", &cost.at(i), &value.at(i));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
scanf("%lld", &w.at(i).at(j));
return;
}
ll dp() {
f.at(0).at(mov) = 0;
for (int i = 1; i <= n; ++i)
for (int j = cost[i]; j <= (mov<<1)+1; ++j)
for (int k = 0; k < i; ++k)
if (f[k][j - cost[i]] != f[0][0])
f[i][j] = max(f[i][j], f[k][j - cost[i]] + value[i] + w[k][i]);
ll ans = f[0][0];
for (int i = 0; i <= n; ++i)
ans = max(ans, f.at(i).at(m + mov));
if (ans == f[0][0]) ans = -1;
return ans;
}
int main() {
in();
cout << dp();
return 0;
}
|
