P6821 题解
EuphoricStar
·
·
题解
考虑恰好选 k 个子段怎么做。
设恰好选 i 个子段的和最大值为 h_k。可以得到 h_{i + 1} - h_i \le h_i - h_{i - 1}，因为 h_i \to h_{i + 1} 的过程就是多选一个子段，贡献肯定不如上一次选即 h_{i - 1} \to h_i 大。如果它不成立，那我们可以交换 h_{i - 1} \to h_i 和 h_i \to h_{i + 1} 选的段从而得到更大的 h_i，矛盾。
那么 (i, h_i) 构成一个上凸包。接下来是经典的 wqs 二分，二分直线斜率切这个上凸包，dp 一遍求出最大截距，这样二分即可找到过 (k, h_k) 且与上凸包相切的直线方程，就能得到 h_k。
dp 的过程是平凡的。设 f_i 为 [1, i] 个中选了若干个子段，它们的和最大值，设 g_i 为在取到最大值的基础上，选的段数最小值。因为当有一些点和 (k, h_k) 共线时，我们希望最后算出来是最左边的点，从而得到这条直线。
如果只是限制最多选 $k$ 个，那如果 $(k, h_k)$ 在左半边（即最高点的左边），那 $\forall i \in [1, k), h_k \ge h_i$，当作恰好 $k$ 个处理即可；如果它在右半边，二分斜率时下界设置为 $0$，那么它就不能被截到。这种情况，直接求出 $\max\limits_{i = 1}^n h_i$ 即可。这里也可以用上面的 dp 方法。
总时间复杂度 $O(n \log V)$，$V$ 是值域。
```cpp
// Problem: P6821 [PA2012]Tanie linie
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6821
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 1000100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
ll n, m, a[maxn], b[maxn];
lll f[maxn], g[maxn];
inline pair<lll, lll> calc(lll x) {
lll mx = 0, cnt = 1;
for (int i = 1; i <= n; ++i) {
f[i] = f[i - 1];
g[i] = g[i - 1];
lll val = mx + b[i] - x;
if (val > f[i]) {
f[i] = val;
g[i] = cnt;
} else if (val == f[i]) {
g[i] = min(g[i], cnt);
}
val = f[i] - b[i];
if (val > mx) {
mx = val;
cnt = g[i] + 1;
} else if (val == mx) {
cnt = min(cnt, g[i] + 1);
}
}
return make_pair(f[n], g[n]);
}
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
b[i] = b[i - 1] + a[i];
}
lll l = 0, r = 2e15, ans = -inf;
while (l <= r) {
lll mid = (l + r) >> 1;
auto p = calc(mid);
if (p.scd <= m) {
ans = p.fst + m * mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (ans == -inf) {
ans = calc(0).fst;
}
printf("%lld\n", (ll)ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
```