wqs 二分。
设 \(h(x)\) 为,恰好选 \(x\) 个的价值最大值。发现 \((x, h(x))\) 形成一个上凸包,考虑 wqs 二分。
二分斜率,去截这个凸包,\(y\) 轴上截距为 \(h(x) - kx\),于是选一个红点代价是 \(k\)。
做一个 dp,\(f_{i, 0/1}\) 表示前 \(i\) 个点,第 \(i\) 个点染 \(0\) 蓝 \(1\) 红的最大价值。
再记一个 \(g_{i, 0/1}\) 表示最大价值的前提下最少选几个红点,因为有的点可能共线,我们想求出最接近的但是又不超过 \(m\) 的点。
记这个东西的作用是,我们可以知道截的是第几个点。
然后,如果截的点编号 \(\le m\),就计入答案,并且减小斜率;否则增大斜率。这一点由上凸包的性质可知。
然后就做完了。时间复杂度 \(O(n \log V)\)。有略优的 \(O(n \log n)\) 反悔贪心。
code
// Problem: H - Red and Blue Lamps
// Contest: AtCoder - AtCoder Beginner Contest 218
// URL: https://atcoder.jp/contests/abc218/tasks/abc218_h
// Memory Limit: 1024 MB
// Time Limit: 2000 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 unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
ll n, m, a[maxn], f[maxn][2], g[maxn][2];
inline pii calc(ll x) {
f[1][0] = 0;
f[1][1] = -x;
g[1][0] = 0;
g[1][1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j <= 1; ++j) {
f[i][j] = -inf;
for (int k = 0; k <= 1; ++k) {
ll val = f[i - 1][k] + ((j ^ k) ? a[i - 1] : 0) - (j ? x : 0);
if (val > f[i][j]) {
f[i][j] = val;
g[i][j] = g[i - 1][k] + j;
} else if (val == f[i][j]) {
g[i][j] = min(g[i][j], g[i - 1][k] + j);
}
}
}
}
ll mx = -inf, cnt = 0;
for (int i = 0; i <= 1; ++i) {
if (f[n][i] > mx) {
mx = f[n][i];
cnt = g[n][i];
} else if (f[n][i] == mx) {
cnt = min(cnt, g[n][i]);
}
}
return make_pair(mx, cnt);
}
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i < n; ++i) {
scanf("%lld", &a[i]);
}
ll l = -2e9, r = 2e9, ans = -1;
while (l <= r) {
ll mid = (l + r) >> 1;
pii p = calc(mid);
// printf("%lld %lld %lld\n", mid, p.fst, p.scd);
if (p.scd <= m) {
ans = p.fst + m * mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner AtCoder Contest Lamps Bluebeginner atcoder contest lamps contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 332 beginner atcoder contest 334 beginner atcoder contest 310