Beginner Examples.

Table of Contents

  1. Overview
  2. Examples
    1. BZOJ 1096
      1. Description
      2. Solution
    2. BZOJ 1911
      1. Description
      2. Solution
    3. BZOJ 1010
      1. Description
      2. Solution
  3. Summary

Overview

We often meet some problems that every time we try to transfer a status to another, we need variables of both two positions, and some are sumed together while others multiplied together.

If we enumrate every position to get the optimized result, usually an $O(n^2)$ complexity is expected. However, some times we can tranform the equation, and find the monotonicity of status. In most cases, the equation will be tranformed into a linear fuction, thus we can express them in an 2-D surface.

Linear fuctions usually have a slope, so we called this DP method Slope Optimizing.

Examples

BZOJ 1096

Description

Given a line with some factories on it. You can build some repos on several factories with a cost of $C_i$. All products need to be transport to a repo, while they can only be transport to a repo with a larger number.

Transport a unit of product in 1 unit of distance cost 1.

Solution

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <queue>

using namespace std;

typedef long long ll;

const int maxn = 1e+6 + 5;

int n;
ll f[maxn], sum1[maxn], sum2[maxn];
ll p[maxn], x[maxn], c[maxn];
int q[maxn], hd, tl;

inline ll A(int xx)
{
    return f[xx] + sum2[xx];
}
inline ll B(int xx)
{
    return sum1[xx];
}
inline double slope(int x, int y)
{
    return (double)(A(x) - A(y))/(double)(B(x) - B(y));
}
inline ll rd()
{
    register ll x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x;
}

int main()
{
    n = rd();
    for(int i = 1; i <= n; ++i)
    {
        x[i] = rd(); p[i] = rd(); c[i] = rd();
        sum1[i] = sum1[i - 1] + p[i];
        sum2[i] = sum2[i - 1] + p[i] * x[i];
    }
    memset(f, 0x3f, sizeof f); f[0] = 0;
    //hd = tl = 1;
    for(int i = 1; i <= n; ++i)
    {
        while(hd < tl && slope(q[hd + 1], q[hd]) < x[i]) ++hd;
        int j = q[hd]; 
        f[i] = f[j] + x[i] * (sum1[i] - sum1[j]) - sum2[i] + sum2[j] + c[i];
        while(hd < tl && slope(q[tl], q[tl - 1]) > slope(i, q[tl])) tl--;
        q[++tl] = i;
    }
    printf("%lld\n", f[n]);
    return 0;
}

BZOJ 1911

Description

Here

Solution

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cctype>

using namespace std;

typedef long long ll;

const int maxn = 1e+6 + 6;

int n, x[maxn];
int q[maxn], hd, tl;
ll f[maxn], sum[maxn], a, b, c;

inline ll A(int x)
{
    return f[x] + a * sum[x] * sum[x] - b * sum[x];
}
inline ll B(int x)
{
    return 2ll * a * sum[x];
}
inline double slope(int i, int j)
{
    return (double)(A(i) - A(j)) / (double)(B(i) - B(j));
}
inline int rd()
{
    register int x = 0, f = 0; char c = getchar();
    while(!isdigit(c)) { if(c == '-') f = 1; c = getchar();}
    while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return f ? -x : x;
}

int main()
{
    n = rd(); a = rd(); b = rd(); c = rd();
    for(int i = 1; i <= n; ++i)
        x[i] = rd(), sum[i] = sum[i - 1] + x[i];
    memset(f, 0xcf, sizeof f); f[0] = 0;
    for(int i = 1; i <= n; ++i)
    {
        while(hd < tl && slope(q[hd], q[hd + 1]) <= sum[i]) hd++;
        int j = q[hd];
        f[i] = f[j] + a * (sum[i] - sum[j]) * (sum[i] - sum[j]) + b * (sum[i] - sum[j]) + c;
        while(hd < tl && slope(q[tl - 1], q[tl]) >= slope(q[tl], i)) tl--;
        q[++tl] = i;
    }
    printf("%lld\n", f[n]);
    return 0;
}

BZOJ 1010

Description

Here

Solution

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using std::min;
using std::max;
using std::swap;
using std::memset;

typedef long long ll;

const int maxn = 50005;

int n,l;
ll L,s[maxn],f[maxn];
int q[maxn],c[maxn];

inline double calc(int y,int x)
{
    return (f[x] + (s[x] + L)*(s[x] + L) - f[y] - (s[y] + L)*(s[y] + L))/(2.0 * (s[x] - s[y]));
}

int main()
{
    scanf("%d%d",&n,&l);
    L = l + 1;
    for(int i = 1; i <= n; ++i) scanf("%d",&c[i]),s[i] = s[i - 1] + c[i];
    for(int i = 1; i <= n; ++i) s[i] += i;
    int h = 1, t = 1;q[1] = 0;
    for(int i = 1; i <= n; ++i)
    {
        while(h < t && calc(q[h], q[h + 1]) <= s[i])h++;
        int tmp = q[h];
        f[i] = f[tmp] + (s[i] - s[tmp] - L) * (s[i] - s[tmp] - L);
        while(h < t && calc(q[t],i) < calc(q[t - 1],q[t]))t--;
        q[++t] = i;
    }
    printf("%lld\n",f[n]);
    return 0;
}

Summary

Writing down the equation and move variables.

Then deal it with monotonic deque.