HDU 2829 (斜率优化)

题意:把一个序列分成m段, 使得每段的花费和最小. 某一段的花费等于这段里任意两个数字的乘积和.

看着就很斜率优化的题目. 假设$s_i$表示$\sum _{j=1}^ia_j$, $c_i$表示i到j这一段的cost, 那么有 $$cost(i, j)=c_j-c_i-\sum _{p=1}^j \sum_{q=j+1}^ia_p*a_q=c_i-c_j-s_j\times (s_i-s_{j})$$

转移的式子是$f_{i,k}=min\left\{ f_{j,k-1}+cost_{i,j+1}\big|j<i \right\}$, 然后整理$j$比$k(k\leq j)$优的条件(第二维表示之前已经有了多少个断点) $$f_{j,p-1}+c_i-c_j-s_j\times (s_i-s_j)\leq f_{k, p-1}+c_i-c_k-s_k\times (s_i-s_k)$$

整理一下 $$\frac{f_{j,p-1}-c_j-f_{k,p-1}+c_k}{s_j-s_k}\leq s_i$$

这东西看着就很斜率, 然后就是一般的斜率优化了.

#include <bits/stdc++.h>
using namespace std;

#define maxn 1111
long long dp[maxn][maxn];
int n, m, que[maxn];
long long a[maxn], sum[maxn], cost[maxn];

long long up (int i, int j, int k) {
    return dp[i][k]-cost[i]+sum[i]*sum[i] - (dp[j][k]-cost[j]+sum[j]*sum[j]);
}

long long down (int i, int j, int k) {
    return sum[i]-sum[j];
}

int main () {
    while (scanf ("%d%d", &n, &m) == 2 && n+m) {
        sum[0] = 0;
        for (int i = 1; i <= n; i++) scanf ("%lld", &a[i]), sum[i] = sum[i-1]+a[i];
        cost[1] = 0;
        for (int i = 2; i <= n; i++) cost[i] = cost[i-1]+sum[i-1]*a[i];
        for (int i = 1; i <= n; i++) dp[i][0] = cost[i];

        for (int k = 1; k <= m; k++) {
            int L = 0, R = 0;
            que[R++] = 0;
            for (int i = 1; i <= n; i++) {
                while (L+1 < R && up (que[L+1], que[L], k-1) <= sum[i]*down (que[L+1], que[L], k-1))
                    L++;
                int j = que[L];
                dp[i][k] = dp[j][k-1] + cost[i] - cost[j] - sum[j]*(sum[i]-sum[j]);
                while (L+1 < R && up (i, que[R-1], k-1)*down (que[R-1], que[R-2], k-1) <=
                       up (que[R-1], que[R-2], k-1)*down (i, que[R-1], k-1))
                    R--;
                que[R++] = i;
            }
        }
        printf ("%lld\n", dp[n][m]);
    }
    return 0;
}