题目翻译

有一个长度为 $n(n\leq 500)$ 的序列，你可以砍 $m(0\leq m\lt n)$ 刀将其分为 $m+1$ 段，令每一段 $[l,r]$ 的贡献为 $\sum\limits_{i=l}^r \sum\limits_{j=i+1}^r a_i\times a_j$，一个序列的答案是每一段的贡献之和，求最小的答案。

题目思路

设 $f_{i,j}$ 表示前 $i$ 个位置割 $j$ 刀的最小答案。

转移是很显然的，枚举上一次断在哪里，$f_{i,j}\gets \min\limits_{k=0}^{i-1}f_{k,j-1}+calc(k+1,i)$。其中 $calc(l,r)$ 是 $[l,r]$ 的贡献。

不考虑 $calc$，转移是 $n^3$ 的，可以通过。但是这个 $calc$ 我们无法快速计算。

但是我们发现这个 $calc$ 被调用了 $n^3$ 次却至多只有 $n^2$ 个答案，所以我们考虑预处理 $calc(l,r)$ 记为 $g_{l,r}$。

$calc$ 有一个显然的 $\mathcal O(n^2)$ 降为 $\mathcal O(n)$ 的做法。根据乘法分配律，我们只关心这个数乘了多大的数，不关心具体乘了谁，记录前缀和，快速得到一个区间内的 $\sum a_i$ 即可 $\mathcal O(n)$ 求出单个 $calc$。

完整代码

#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkmn(T &x, T y) { x = min(x, y); }
int n, m;
int a[520];
int f[520][520];
int g[520][520];
int pre[520];
int calc(int l, int r)
{
    int ret = 0;
    for (int i = l; i <= r; i++)
        ret += a[i] * (pre[r] - pre[i]);
    return ret;
}
int main()
{
    memset(f, 0x3f, sizeof(f));
    cin >> n >> m;
    m++;
    for (int i = 1; i <= n; i++)
        cin >> a[i], pre[i] = pre[i - 1] + a[i];
    for (int l = 1; l <= n; l++)
        for (int r = l; r <= n; r++)
            g[l][r] = calc(l, r);
    memset(f[0], 0, sizeof(f[0]));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= min(i, m); j++)
            for (int k = 0; k < i; k++)
                chkmn(f[i][j], f[k][j - 1] + g[k + 1][i]);
    cout << f[n][m] << endl;
    return 0;
}