-
Notifications
You must be signed in to change notification settings - Fork 4
/
2087.cpp
57 lines (53 loc) · 1.25 KB
/
2087.cpp
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
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3005;
int n, k, x[N];
ll g[N][N], h[N][N];
vector<ll> fc, fp;
ll calc(int l, int r) {
int mid = (l + r) >> 1;
return g[l][mid] + h[r][mid + 1];
}
void compute(int l, int r, int optl, int optr) {
if (l > r) return;
int mid = (l + r) >> 1;
pair<ll, int> best = {1e18, -1};
for (int k = optl; k <= min(optr, mid - 1); ++k) {
best = min(best, {fp[k] + calc(k, mid), k});
}
fc[mid] = best.first;
compute(l, mid - 1, optl, best.second);
compute(mid + 1, r, best.second, optr);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> x[i];
}
for (int i = 1; i <= n; ++i) {
g[i][i] = h[i][i] = 0;
for (int j = i + 1; j <= n; ++j) {
g[i][j] = g[i][j - 1] + 1LL * (j - i) * x[j];
}
for (int j = i - 1; j >= 1; --j) {
h[i][j] = h[i][j + 1] + 1LL * (i - j) * x[j];
}
}
fc.resize(n + 1);
fp.resize(n + 1);
for (int i = 1; i <= n; ++i) {
fp[i] = h[i][1];
}
for (int i = 2; i <= k; ++i) {
compute(i, n, i - 1, n);
fc.swap(fp);
}
ll ans = 1e18;
for (int i = k; i <= n; ++i) {
ans = min(ans, fp[i] + g[i][n]);
}
cout << ans;
return 0;
}