斜率优化dp

ACM › 学习笔记 › DP
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// 斜率优化

// 对于dp[i]=max/min(f(j)+g(j)*h(i)+H(i))形式

// 为简化描述我们可以只考虑min情况
// 我们对式子中不同的j作差
// 这里姑且用j与k表示
// 不妨设k>j
// 得到差f(k)-f(j)+h(i)*(g(k)-g(j))

// 如果k优于j那么上式<=0
// f(k)-f(j)+h(i)*(g(k)-g(j))<=0
// 如果g函数满足单调，为了方便 我们假设他单调增
// 则【f(k)-f(j)】/【g(k)-g(j)】<=h(i)
// 斜率找到，就是最大且小于h(i)的一组相邻点的斜率，这时的右端点就是dp转移式所要的东西

// 总而言之，当且仅当转移方程满足dp[i]=max/min(f(j)+g(j)*h(i)+H(i))形式且g函数单调
// 我们就可以斜率优化 

// 重在思维与推导，不在板子，此板子仅供参考
#include<bits/stdc++.h>

using namespace std;
#define ll long long
const int maxn = 5e4;
long long Q[maxn], dp[maxn], s[maxn];

long long f(int j) {
    return dp[j] + (j + s[j]) * (j + s[j]);
}

double Slope(long long j, long long k)   //求斜率
{
    return double(f(k) - f(j)) / (k + s[k] - j - s[j]);
}

int main() {
    ll n, L;
    while (~scanf("%lld%lld", &n, &L)) {
        for (int i = 1; i <= n; i++) {
            int tmp;
            scanf("%d", &tmp);
            s[i] = s[i - 1] + tmp;
        }

        int Left = 1, Right = 1;
        Q[1] = 0;
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            while (Left < Right && Slope(Q[Left], Q[Left + 1]) <= 2 * (s[i] + i - L - 1))
                Left++; //维护队首（删除非最优决策）
            int j = Q[Left];
            dp[i] = dp[j] + (i - j - 1 + s[i] - s[j] - L) * (i - j - 1 + s[i] - s[j] - L); //计算当前f
            while (Left < Right && Slope(Q[Right - 1], Q[Right]) >= Slope(Q[Right], i))
                Right--; //维护队尾（维护下凸包性质）
            Q[++Right] = i; //入队
        }
        printf("%lld\n", dp[n]);
    }
    return 0;
}
// solved pzoj 1010