SnackOI R1-D 战争与和平 题解
liangjindong0504
·
·
个人记录
闲话
这题在测试人员里面通过人数第二多。
n 较小的部分分
爆搜每个元素属于第几组，期望得分 15pts。
状压，时间复杂度 O(4^n)，期望得分 30pts。
优化一下枚举子集，时间复杂度 O(3^n)，期望得分 35pts。
特殊性质
特殊性质 BC 一起看吧。
容易发现区间长度取 1，2 的时候是非常优秀的，贡献很大，以此进行贪心即可。期望得分 45pts。
特殊性质 AD 好像没啥特殊做法。
正解
发现，我们将数组排序后，一定会选择多个连续的段。
实际上这个很好理解，因为如果我们以此分完段后，有两组交换了一个元素，那么贡献一定不优。所以排序后取连续段是最优的。
我们发现 dp 式子好像非常有趣，就是 $dp_i = \max\{dp_{j-1} + s_i - s_{j - 1} - a_i + a_j\}$，$s$ 为前缀和数组。发现这个东西可以用线段树或者 set 优化，时间复杂度 $O(n \log n)$，期望得分 $85pts$。
用单调队列优化，时间复杂度线性，期望得分 $100pts$。实际上上面的复杂度都是除了排序以外的复杂度。所以正解实际上还是 $O(n \log n)$ 的，只是常数很小而已。
代码献上。
```cpp
#include <bits/stdc++.h>
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
const int MAXN = 5e6 + 10;
const i64 INF = 1e18;
int n, l, r;
int h, t;
int q[MAXN];
i64 a[MAXN];
i64 dp[MAXN];
i64 sum[MAXN];
i64 f (int x) {
return dp[x] - sum[x] + a[x + 1];
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cin >> n >> l >> r;
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
}
std::sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + a[i];
}
h = 1, t = 0;
if (1 - r <= 0 && 0 <= 1 - l) {
q[++t] = 0;
}
for (int i = 1; i <= n; ++i) {
while (h <= t && q[h] < i - r) {
++h;
}
if (h <= t) {
int j = q[h];
dp[i] = f(j) + sum[i] - a[i];
} else {
dp[i] = -INF;
}
int id = i - l + 1;
if (id >= 0) {
while (h <= t && f(q[t]) <= f(id)) {
--t;
}
q[++t] = id;
}
}
std::cout << dp[n];
return 0;
}
```