[HDU 2829]Lawrence

Description

题库链接

给你一个长度为 \(n\) 的数组 \(a\)。你需要将其划分为 \(m+1\) 段，每一段的贡献为该段内所有元素两两乘积的和。求所有划分中贡献最少时的贡献和。

\(1\leq m< n\leq 1000\)

Solution

假设前 \(i\) 个数分为 \(j\) 段的最少贡献为 \(f_{i,j}\)，那么可以列出 DP 方程 \(f_{i,j}=\min\{f_{k-1,j-1}+w(k, i)\}\)。

这里的 \(w\) 其实就是这一段所有元素的和平方减去平方和再除以 2。显然 \(w\) 是满足四边形不等式的。那么可以用四边形不等式定理优化 DP，具体可以参考[IOI 2000]邮局这题题解。时间复杂度为 \(O(n^2)\)。

由于 \(w\) 是一个二次函数形式的式子，也可以斜率优化，复杂度是 \(O(nm)\) 的。

Code

#include 
#define ll long long
using namespace std;
const int N = 1005;

int n, m, a[N], s[N][N];
ll f[N][N], sum[N];

int main() {
    while (~scanf("%d%d", &n, &m) && (n || m)) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            sum[i] = sum[i-1]+1ll*a[i]*a[i];
            a[i] += a[i-1];
        }
        for (int i = 0; i <= n; i++) {
            s[i][0] = 1;
            f[i][0] = (1ll*a[i]*a[i]-sum[i])/2;
            for (int j = 1; j <= m; j++)
                f[i][j] = 1e12;
        }
        for (int i = 1; i <= m; i++) s[n+1][i] = n;
        f[0][0] = 0;
        for (int j = 1; j <= m; j++)
            for (int i = n; i >= 1; i--)
                for (int k = s[i][j-1]; k <= s[i+1][j]; k++)
                    if (f[i][j] > f[k-1][j-1]+(1ll*(a[i]-a[k-1])*(a[i]-a[k-1])-sum[i]+sum[k-1])/2) {
                        f[i][j] = f[k-1][j-1]+(1ll*(a[i]-a[k-1])*(a[i]-a[k-1])-sum[i]+sum[k-1])/2;
                        s[i][j] = k;
                    }
        printf("%lld\n", f[n][m]);
    }
    return 0;
}