代码呢
by wxy_god @ 2018-09-27 18:35:33
@[我是一个垃圾](/space/show?uid=89396)
~~那个链接里有~~
``` cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 500000 + 10;
int n, k; ll _a[N], a[N];
struct T {
ll res, cnt;
T(ll res = 0, ll cnt = 0) : res(res), cnt(cnt) { }
T operator + (ll x) {
return T(res + x, cnt + 1);
}
} f[N][2];
bool operator < (T a, T b) {
if(a.res != b.res) return a.res < b.res;
else return a.cnt > b.cnt;
}
T check(ll cost) {
for(int i = 1 ; i <= n ; ++ i) a[i] = _a[i] - cost;
for(int i = 1 ; i <= n ; ++ i) {
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = f[i - 1][0] + a[i];
}
return max(f[n][0], f[n][1]);
}
int main() {
scanf("%d%d", &n, &k);
for(int i = 1 ; i <= n ; ++ i) scanf("%lld", &_a[i]);
ll l = -1e17, r = -l, ans = 0;
// l = -10, r = 10;
// for(int i = -10 ; i <= 10 ; ++ i) cout << check(i).cnt << ' '; cout << endl; exit(0);
// T t = check(2);
// cout << t.res << ' ' << t.cnt << endl; exit(0);
while(l <= r) {
ll mid = (l + r) / 2;
T t = check(mid);
if(t.cnt <= k) {
ans = max(ans, t.res + t.cnt * mid);
r = mid - 1;
} else {
l = mid + 1;
}
}
printf("%lld\n", ans);
}
```
by nekko @ 2018-09-27 18:41:09
~~已解决，可以忽略掉这个帖子了~~
by nekko @ 2018-10-08 21:13:45