bzoj3675-序列分割

题意

一个长度为n的非负整数序列,要求分割成k+1段,每次分割获得的价值是:分割后两端和的乘积。求获得的最大价值

$1 \leq n \leq 1e5, 1 \leq k \leq 200$

分析

最终答案和分割的次序是没有关系的。

证明可以考虑分割结束后重新合并的过程,发现合并的次序并没有影响,因此分割时的次序也不影响答案。

因为k只有200,所以很容易想到一个$O(nk)$的dp。

$dp[k][n]$表示第k次分割前n个元素可获得的最大价值。

$$dp[k][n] = Max( dp[k-1][j] + pre[j] \times ( pre[n] - pre[j])), j \in [k-1,n-1]$$

继续化简即可得到一个斜率不等式,而且是可以用单调队列优化的那种噢!

如果对斜率优化不清楚的话,可以参考我的另一篇博客:优化方法。

代码

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
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define my_unique(a) a.resize(distance(a.begin(), unique(a.begin(), a.end())))
#define my_sort_unique(c) (random_shuffle(c.begin(), c.end())), my_unique(c)
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 1e5 + 5;
int a[maxn];
ll pre[maxn], dp[2][maxn];

inline double slope(int j, int k, int i) {
double mj = dp[(i & 1) ^ 1][j] - pre[j] * pre[j];
double mk = dp[(i & 1) ^ 1][k] - pre[k] * pre[k];
if (pre[j] == pre[k]) return (mj - mk) > 0 ? 10000 : -1e9 - 5;
return (mj - mk) / (pre[j] - pre[k]);
}

int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
// */
std::ios::sync_with_stdio(false);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", a + i), pre[i] = pre[i - 1] + a[i];
for (int i = 1; i <= m; i++) {
int l = 1, r = 1;
vector<int> q(n + 2);
q[1] = i - 1;
for (int t = i; t <= n; t++) {
while (l < r && slope(q[l], q[l + 1], i) > -pre[t]) l++;
int idx = q[l];
dp[i & 1][t] =
dp[(i & 1) ^ 1][idx] + pre[idx] * (pre[t] - pre[idx]);
while (l < r && slope(q[r - 1], q[r], i) < slope(q[r], t, i)) r--;
q[++r] = t;
}
}
printf("%lld\n", dp[m & 1][n]);
}
Thank you for your support!