P1776 宝物筛选

1. 单调队列优化版

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
#include<bits/stdc++.h>
using namespace std;
const int MAXW = 4e4;

template <typename T> 
inline void read(T &a) {
    register char c;while (c = getchar(), c < '0' || c > '9');register T x(c - '0');while (c = getchar(), c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);}a = x;  
}
template <typename T, typename ...Argv>
inline void read(T &n, Argv &...argv) {
    read(n), read(argv...);
}

int le, ri; pair<int, int> q[MAXW + 10];
inline void Init() {
    le = 1;
    ri = 0;
}
inline void Push_back(int x, int idx) {
    while (le <= ri && q[ri].first <= x) {
        --ri;
    }
    q[++ri] = make_pair(x, idx);
}
inline int Front(int idx) {
    while (le <= ri && q[le].second < idx) {
        ++le;
    }
    return q[le].first;
}

int n, W, d[MAXW + 10];
signed main() {
    read(n, W);
    for (int i = 1, v, w, m; i <= n; ++i) {
        read(v, w, m);
        for (int j = 0; j < w; ++j) {
            Init();
            for (int k = 0, l = j; l <= W; ++k, l += w) {
                Push_back(d[l] - k * v, k);
                d[l] = Front(k - m) + k * v;
            }
        }
    }
    printf("%d\n", d[W]);
}

2. 二进制拆分版

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
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXn = 100;
const int MAXW = 40000;

int n, W;
int v_new[MAXn * 10 + 10];
int w_new[MAXn * 10 + 10];
int num_new;
int d[MAXW + 10];

inline int read() {
    register char c;
    for (c = getchar(); (c < '0' || c>'9') && c != '-'; c = getchar());
    register bool f = c == '-';
    register int s = f ? 0 : c - '0';
    for (c = getchar(); c >= '0' && c <= '9'; c = getchar())s = (s << 3) + (s << 1) + c - '0';
    return f ? -s : s;
}

void bin_divide(int v, int w, int num, int v_new[], int w_new[], int& num_new) {
    for (int i = 1; num >= i; i <<= 1) {
        v_new[++num_new] = v * i;
        w_new[num_new] = w * i;
        num -= i;
    }
    if (num > 0) {
        v_new[++num_new] = v * num;
        w_new[num_new] = w * num;
    }
}

void rec(int v[], int w[], int W, int num) {
    for (int i = 1; i <= num; i++) {
        for (int j = W; j >= w[i]; j--)    d[j] = max(d[j], d[j - w[i]] + v[i]);
    }
}

int eva_maxV(int d[], int W) {
    int ans = -INF;
    for (int i = 0; i <= W; i++)   ans = max(ans, d[i]);
    return ans;
}

int main() {
    n = read();
    W = read();
    int v, w, num;
    for (int i = 1; i <= n; i++) {
        v = read();
        w = read();
        num = read();
        bin_divide(v, w, num, v_new, w_new, num_new);
    }
    rec(v_new, w_new, W, num_new);
    cout << eva_maxV(d, W);
}