练手
序列分割
刚搞了那么久 dp ，来练练
题意
给定 $n \le 10^5$ 个数 $a_i \le 10^4$ ，最初所以数就是一块，每次操作可以选择一个长度超过 $1$ 的块把它分成长度 $\ge 1$ 的两块，得到的分数就是新产生的块的元素和的乘积，求操作 $k \le 200$ 次后的最大得分
思路
一看是区间 dp ，但仔细想想，发现最后答案和操作顺序无关：
如一个区间 $[a, b, c]$ （其中 $a, b, c$ 代表了一段数），我们用两次操作把它们分成 $[a], [b], [c]$ ，不管是 $[a, b, c] \to [a, b], [c] \to [a], [b], [c]$ 还是 $[a, b, c] \to [a], [b, c] \to [a], [b], [c]$ ，你会发现得分都是 $ab + ac + bc$ ，即每个段的得分一定是 $该段和 \times 前面所有数的和$
那么直接设 $d[i, k]$ 表示“前 $i$ 个数分成了 $k$ 段的最大得分”（注意最后应该有 $k + 1$ 段），有：
$$
d[i, k] = \max _{0 \le j < i} (d[j, k - 1] + (sum[i] - sum[j]) * sum[j])
$$
其中 $sum$ 是前缀和
明显 $k$ 是外层（且可以滚动），对于内层考虑何时 $j$ 优于 $p$ ：
$$
\begin{aligned}
d[j] + (sum[i] - sum[j]) * sum[j] & \ge d[p] + (sum[i] - sum[p]) * sum[p] \\
sum[i] & \ge \frac{(sum[j]^2 - d[j]) - (sum[p]^2 - d[p])}{sum[j] - sum[p]} \\
\end{aligned}
$$
故形式二为：
$$
sum[j]^2 - d[j] = sum[i] \times sum[j] - d[i]
$$
直接上斜率优化即可
代码
注意代码 $d$ 的两个维度互换了，因为这样内存访问连续，常数小
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
| #include <bits/stdc++.h>
using LL = long long;
const int N = 1e5 + 5, K = 200 + 5;
int n, k, o, a[N], from[K][N], q[N], hh, tt;
LL sum[N], d[2][N];
LL X(int x){ return sum[x]; }
LL Y(int x){ return sum[x] * sum[x] - d[o][x]; }
bool chkh(int a, int b, LL k){ return (Y(a) - Y(b)) <= k * (X(a) - X(b)); }
bool chkt(int a, int b, int c){ return (Y(a) - Y(b)) * (X(b) - X(c)) <= (Y(b) - Y(c)) * (X(a) - X(b)); }
int main()
{
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i];
for (int i = 1, j; i <= k; ++i, o ^= 1)
for (q[hh = tt = 1] = i - 1, j = i; j <= n; ++j)
{
for (; hh < tt && chkh(q[hh + 1], q[hh], sum[j]); ++hh);
d[o ^ 1][j] = d[o][(from[i][j] = q[hh])] + (sum[j] - sum[q[hh]]) * sum[q[hh]];
for (; hh < tt && chkt(j, q[tt], q[tt - 1]); --tt);
q[++tt] = j;
}
printf("%lld\n", d[o][n]);
for (int i = k, pos = n; i >= 1; --i) printf("%d ", pos = from[i][pos]);
return 0;
}
|