题目链接：P3648 [APIO2014] 序列分割
（注：由于本题解的状态转移方程需要用到 \(k\)，所以原题中的 \(k\) 对应本题解中的 \(m\)。）
给你一个长度为 \(n\) 的序列 \(A_1,A_2,...,A_n\)，一开始把它看作一个块。初始你的分数为 \(0\)，现在你需要进行下列操作恰好 \(m\) 次：
- 选一个块，并从一处断开，使得断开的两个块不为空。此时这两个块里的数的和的乘积将加到你的分数里。
求最终分数的最大值，并输出断开的位置。
\(2 \le n \le 10^5,1\le m\le\min\{n-1,200\},0\le A_i\le 10^4\)。
转化
这个分数的计算有点绕啊！我们考虑一下两个位置 \((i,j)\) 的贡献吧：不难发现，当且仅当这两个位置最终不在一个块内时，对答案产生 \(A_i \times A_j\) 的贡献。
还是很难算，每个位置要统计一下外面所有位置的贡献。那直接反过来不就好了，我们直接累加每个块内的和的平方。那么答案就是：
\[\frac{(\sum_{i=1}^{n} A_i)^2-sum}{2} \]于是我们就成功把原问题转化为了这么一个问题：
有一个长度为 \(n\) 的序列，现在要将序列划分为 \(m+1\) 段，最小化各段和的平方之和。
DP
考虑 dp，设 \(f_{k,i}\) 表示第 \(k\) 段的末尾是 \(i\)，当前的总和的最小值。
则有
\[f_{k,i}=\min_{k\le j\le i}\{f_{k-1,j - 1} + (\sum_{l=j}^i A_l)^2\} \]此时 \(f_k\) 是有决策单调性（即 \(i<j\) 两个位置的决策点 \(op_i\le op_j\)）的，下面讲讲为什么：
四边形不等式与决策单调性
假设我们要解决如下一类问题：
\[f_{i} = \min_{1\le j \le i} w(i,j) \]若对于 \(a<b<c<d\)，有
\[w(a,c)+w(b,d)\le w(a,d)+w(b,c) \]那么称函数 \(w\) 满足「四边形不等式」。此时 \(f_i\) 具有决策单调性。证明不再赘述，想了解可以前往 OI Wiki - 四边形不等式优化。
回到这题，假设当前外层循环是 \(k\)，我们令 \(w(i,j)\) 表示 \(f_{k,i - 1} + \sum_{l=j}^i A_l)^2\)。那么它是否满足四边形不等式呢？
假设有四个位置 \(a\le b\le c\le d\)，并且有
\[\begin{cases} X=\sum_{a\le i < b} A_i\\ Y=\sum_{b\le i\le c} A_i\\ Z=\sum_{c < i\le d} A_i \end{cases} \]则
\[\begin{aligned} w(a,c)+w(b,d)&=f_{k,a-1}+(X+Y)^2+f_{k,b-1}+(Y+Z)^2\\ &=f_{k,a-1}+f_{k,b-1}+X^2+2Y^2+Z^2+2XY+2YZ\\ \\ w(a,d)+w(b,c)&=f_{k,a-1}+(X+Y+Z)^2+f_{k,b-1}+Y^2\\ &=f_{k,a-1}+f_{k,b-1}+X^2+2Y^2+Z^2+2XY+2YZ+2ZX \end{aligned} \]所以有
\[w(a,c)+w(b,d) \le w(a,d)+w(b,c) \]即 \(w\) 满足四边形不等式，故 \(f_k\) 具有决策单调性。
所以就可以放心分治优化 dp 了。对于每次递归 \((l,r,x,y)\) 表示 \([l,r]\) 的 dp 值待计算，并且决策点位于 \([x,y]\)。每次遍历 \([x,y]\)，计算 \(mid=\lfloor\frac{l+r}{2}\rfloor\) 位置的 dp 值，然后递归 \((l,mid-1,x,op_{mid})\) 和 \((mid+1,r,op_{mid},y)\)。
时间复杂度 \(O(mn\log n)\)。
// Author: Aquizahv
#include <bits/stdc++.h>
#define ll long long
#define sq(x) (x) * (x)
using namespace std;
const int N = 1e5 + 5, M = 205;
int n, m, a[N], k, op[M][N];
ll sum[N], dp[M][N];
ll cal(int l, int r)
{
return sq(sum[r] - sum[l - 1]);
}
void solve(int l, int r, int x, int y)
{
int mid = (l + r) >> 1;
for (int i = x; i <= y && i <= mid; i++)
{
ll w = dp[k - 1][i - 1] + cal(i, mid);
if (dp[k][mid] > w)
{
dp[k][mid] = w;
op[k][mid] = i;
}
}
if (l < mid)
solve(l, mid - 1, x, op[k][mid]);
if (mid < r)
solve(mid + 1, r, op[k][mid], y);
}
int main()
{
cin >> n >> m;
m++;
for (int i = 1; i <= n; i++)
scanf("%d", a + i), sum[i] = sum[i - 1] + a[i];
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for (k = 1; k <= m; k++)
solve(1, n, 1, n);
cout << (sq(sum[n]) - dp[m][n]) / 2 << endl;
vector<int> res;
int pre = op[m][n] - 1;
for (k = m ; k > 1; k--)
{
res.push_back(pre);
pre = op[k - 1][pre] - 1;
}
while (!res.empty())
{
printf("%d ", res.back());
res.pop_back();
}
return 0;
}