「poj 3709」K-Anonymous Sequence (斜率优化DP，延迟加入决策)

发表于 | 分类于 | | + s

poj 3709
题意：给定一个数列 $a$， 分成若干段，每段至少有$k$个数， 将每段中的数减少至所有数都相同， 求最小的变化量

设$dp(i)$为前$i$个的最小变化量。
则
$$
dp(i)=\min_{i-j \leq k}(dp(j)+\operatorname{sum}(i)-\operatorname{sum}(j)-i \cdot a_{j+1} +j \cdot a_{j+1})
$$

显然可以斜率优化。决策表示为$(a_{j+1}, dp(j)-sum(j)+j \cdot a_{j+1})$，即可算斜率。
注意$i-j \leq k$的限制，我们可以考虑延迟加入决策(具体看代码)，预处理$[0,2k]$的答案。

知识点
对于这种有限制的斜率优化可以考虑延迟加入决策

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

int T;

namespace flyinthesky {

    const LL INF = 3000000000000ll; 

    LL n, k, a[500000 + 5], sum[500000 + 5];
    LL dp[500000 + 5], q[500000 + 5];

    LL getx(LL j) {return a[j + 1];}
    LL gety(LL j) {return dp[j] - sum[j] + j * a[j + 1];}

    void clean() {
        ms(sum, 0);
    }
    int solve() {

        clean();
        cin >> n >> k;
        for (LL i = 1; i <= n; ++i) scanf("%lld", &a[i]), sum[i] = sum[i - 1] + a[i];
        sort(a + 1, a + 1 + n);

        ms(dp, 0);
        for (LL i = 1; i < k; ++i) dp[i] = INF;
        for (LL i = k; i <= 2 * k; ++i) dp[i] = sum[i] - i * a[1]; // 预处理

        LL l = 1, r = 1;
        q[1] = k;
        for (LL i = 2 * k; i <= n; ++i) {
            while (l < r && (gety(q[l + 1]) - gety(q[l])) <= i * (getx(q[l + 1]) - getx(q[l]))) ++l;
            dp[i] = dp[q[l]] + sum[i] - sum[q[l]] - i * a[q[l] + 1] + q[l] * a[q[l] + 1];
            while (l < r && (gety(q[r]) - gety(q[r - 1])) * (getx(i - k + 1) - getx(q[r])) >= (gety(i - k + 1) - gety(q[r])) * (getx(q[r]) - getx(q[r - 1]))) --r; // 延迟加入决策
            q[++r] = i - k + 1; // 延迟加入决策
        }

        printf("%lld\n", dp[n]);

        return 0;
    }
}
int main() {
    scanf("%d", &T);
    while (T--) flyinthesky::solve();
    return 0;
}
------ 本文结束 ------