校内模拟赛 10.08

做题记录
, ,

abcd

描述

有 4 个长度为 $N$ 的数组 $a,b,c,d$。现在需要你选择 $N$ 个数构成数组 $e$，满足对所有 $i$ 有 $ a_i \le e_i \le b_i $ 并且满足约束 $ \displaystyle \sum_{i=1}^N e_i c_i = 0 $。
目标是使得 $ \displaystyle \sum_{i=1}^N e_i d_i $ 最大化。题目保证至少存在一个可行解。

输入

输入共 $N+1$ 行。
第 $1$ 行包含一个正整数 $N$。
第 $i+1$ 行包含 4 个整数 $a_i\; b_i\; c_i\; d_i$（按顺序）。

输出

输出共 $1$ 行，包含 $1$ 个整数，表示所给目标的最大值。

约束

  • 对于 $20\%$ 的数据：$N \le 10,\ -2 \le a_i < b_i \le 2$；
  • 对于 $60\%$ 的数据：$N \le 50,\ -20 \le a_i < b_i \le 20$；
  • 对于 $100\%$ 的数据：$N \le 200,\ -25 \le a_i < b_i \le 25,\ 1 \le c_i \le 20,\ 0 \le d_i \le 100000$。

样例（分组）

样例组 Sample Input Sample Output
#1 
5
-1 1 2 5
-2 2 1 2
0 1 1 3
-2 -1 3 10
-2 2 3 9
 
2
#2 
10
1 10 1 7
-10 10 2 0
-10 10 2 2
-10 10 2 0
1 10 1 0
-10 10 2 0
10 10 2 0
1 10 1 0
-10 10 2 0
1 10 1 0
 
90
#3 
10
1 10 1 0
-10 10 2 2
-10 10 2 2
-10 10 2 2
1 10 1 0
-10 10 2 2
-10 10 2 2
1 10 1 0
-10 10 2 2
1 10 1 0
 
-4

这题显然转化为多重背包问题，要求背包内物品“体积”和严格为 $0$，计算价值的最大值。
形式化的，每种物品有体积 $c_i$，价值 $d_i$，数量 $b_i-a_i$，最终答案为 $(\sum\limits_{i=1}^n e_i \cdot a_i) + f[0]$，其中 $f[0]$ 为体积和为 $0$ 时物品最大价值。

理论上，我们可以使用 SIMD AVX2 优化通过此题，我赛时也是这样写的。
二进制分组也不妨是一个优秀的选择。
但是考虑到如果数据更加极限，比如调小 $c_i$ 调大 $b_i-a_i$，那这两种都可以被卡掉。
所以，这题应该使用优先队列优化多重背包计算。

注意到，朴素多重背包转移：

1
2
3
4
for (int i = 1; i <= n; i++)
    for (int j = mn; j <= mx; j++)
        for (int k = 1; k <= amount[i]; k++)
            update_max(f[i][j], f[i - 1][j - k * size[i]] + k * value[i]);

这其中的 j 转移的时候都是从 $[j] \pmod{size_i}$ 这个同余类转移过来的，也就是说，我们每次都是减去了 $size_i$ 的整数倍。
所以我们可以更加快速地转移 f[i][j]。容易想到一些区间算法，但是不如二进制分组，所以不加以阐述。

我们考虑使用单调队列维护对于 g[mod][div] = f[i-1][div * size[i] + mod] - value[i] * div 的每个子数组（即 g[0], g[1], g[2], …, g[size[i]-1]），其中 $\texttt{div} \in \mathbb N, \texttt{ mod} \in [0, size_i]$。
这样我们每次更新 f[i][j] 转移式子就会变成 $($ $\max\limits_{k=0}^{size_i-1}$ g[j % size[i]][j / size[i] - k] $)$ $+$ value[i] * j / size[i]]。
其实你展开后发现，那个后面的 $value_i$ 系数 一减一加，刚刚好就剩下了 $k$。这就是维护 g 的妙处。

容易发现，如果我们枚举 $j$，那么 f[i][j] 的计算只和 g[j % size[i]] 中的值有关，而且因为 j 是从小往大枚举的，j / size[i] 是非递减的。所以我们的 g 就可以愉快地使用单调队列处理啦！每次询问队首获得最大值，保证队列递减，这样一定是最优的。注意！队首当数量超过的时候也要弹出，确保合法。
注意：实际实现的时候不要傻乎乎地用 g[][]，这样没有必要，直接维护的时候加减 size[i] 就可以了，但是这样可能会导致 Cache Miss，引发性能问题，但我觉得和 vector 的性能应该差不了多少。这题你要想用 g[][] 只能 vector。
最终时间复杂度为 $\mathcal O(n \cdot (\sum\limits_{i=1}^n (b_i-a_i) \cdot c_i))$ 事实上，使用单调队列优化的多重背包在这题里面还没有暴力快

Code (SIMD AVX2) 
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
#include <stdio.h>
#include <string.h>
#include <immintrin.h>
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
constexpr int N = 205, M = 100005;
int a[N], b[N], c[N], d[N];
int f[2][M * 2];
#define Pre(x) f[i&1^1][(x)+M]
#define Now(x) f[i&1][(x)+M]
inline void umin(int &x, const int y) { x = x < y ? x : y; }
inline void umax(int &x, const int y) { x = x > y ? x : y; }
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d%d", a+i, b+i, c+i, d+i);
    memset(f, -0x3f, sizeof(f) >> 1);
    f[0][0+M] = 0;
    int mn = 0, mx = 0;
    for (int i = 1; i <= n; i++) {
        memset(f[i&1], -0x3f, sizeof(f) >> 1);
        int *now = f[i&1] + M, *pre = f[i&1^1] + M;
        for (int e = a[i]; e <= b[i]; e++) {
            const __m256i addshift = _mm256_set1_epi32(e * d[i]);
            int* nowshift = now + e * c[i];
            int j = mn;
            for (int jl = mx - 7; j <= jl; j += 8) {
                __m256i fnow = _mm256_loadu_si256((__m256i*)(nowshift + j));
                __m256i fpre = _mm256_loadu_si256((__m256i*)(pre + j));
                _mm256_storeu_si256((__m256i*)(nowshift + j), _mm256_max_epi32(fnow, _mm256_add_epi32(fpre, addshift)));
            }
            for (; j <= mx; j++)
                umax(nowshift[j], pre[j] + e * d[i]);
            /* for (int j = mn; j <= mx; ++j) {
                int tp = j + e*c[i];
                umax(Now(tp), Pre(j) + e * d[i]);
            } */
        }
        umin(mn, mn + a[i] * c[i]);
        umax(mx, mx + b[i] * c[i]);
    }
    printf("%d\n", f[n&1][0+M]);
    return 0;
}
Code (Monotonic Queue) 
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
#include <stdio.h>
#include <string.h>
#include <algorithm>
constexpr int N = 205, M = 100005;
int a[N], b[N], amount[N], c[N], d[N];
long long f[2][M * 2], g[M * 2];
int l[N], r[N];
int gp[M * 2];
int main() {
    int n;
    scanf("%d", &n);
    int sum = 0, cnt = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", a+i, b+i, c+i, d+i);
        sum += a[i] * d[i];
        cnt += a[i] * c[i];
        amount[i] = b[i] - a[i];
    }
    memset(f, -0x3f, sizeof(f) >> 1);
    f[0][0+M] = 0;
    auto *now = f[1], *pre = f[0];
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < c[i]; j++)
            l[j] = j, r[j] = j - c[i];
        memset(g, -0x3f, sizeof g);
        int mod = 0, div = 0;
        for (int j = 0; j < 2*M; j++) {
            long long tmp = pre[j] - 1ll * d[i] * div;
            while (l[mod] <= r[mod] && div - gp[l[mod]] > amount[i]) l[mod] += c[i];
            while (l[mod] <= r[mod] && g[r[mod]] <= tmp) r[mod] -= c[i];
            g[r[mod] += c[i]] = tmp; gp[r[mod]] = div;
            now[j] = g[l[mod]] + 1ll * d[i] * div;
            // if (now[j] >= -1000000) printf("%d %d: %d %d %lld %lld %lld\n", i, j, gp[l[mod]], gp[r[mod]], g[l[mod]], g[r[mod]], now[j]);
            if (++mod == c[i]) mod = 0, ++div;
        }
        std::swap(now, pre);
    }
    printf("%lld\n", sum + pre[M - cnt]);
    return 0;
}