Chaos Slover 补档计划 - 动态规划

2015.12.02 09:43 Wed| 4 visits oi_2016| ChaosSlover补档计划| Text

BZOJ1096 [ZJOI2007]仓库建设

经典的斜率优化。询问的斜率递增,点的横坐标也递增,那么直接用双端队列维护一个下凸包就好了。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 1000005

int n; int x[N], p[N], c[N];
long long s[N], xp[N], dp[N], y[N];
deque<int> v; deque<double> k;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

double getk(int a, int b)
{
    return (double)(y[a] - y[b]) / (double)(s[a] - s[b]);
}

int main()
{
    cin >> n;
    v.push_back(0);
    for (int i = 1; i <= n; ++i)
    {
        x[i] = read(); p[i] = read(); c[i] = read();
        s[i] = s[i - 1] + p[i]; xp[i] = xp[i - 1] + 1ll * x[i] * p[i];
        dp[i] = c[i] + s[i] * x[i] - xp[i];
        while (!k.empty() && k.front() < x[i])
            v.pop_front(), k.pop_front();
        int t = v.front();
        dp[i] += dp[t] + xp[t] - s[t] * x[i];
        y[i] = dp[i] + xp[i];
        while (!k.empty() && getk(v.back(), i) < k.back())
            v.pop_back(), k.pop_back();
        k.push_back(getk(v.back(), i)); v.push_back(i);
    }
    cout << dp[n] << endl;
    return 0;
}

BZOJ3203 [Sdoi2013]保护出题人

又是一位大神的题解。

列出来那个 DP 方程其实是很简单的 0.0。(然而我最开始列麻烦了,之后还傻了吧唧地展开,然后就不知道怎么做了)

观察那个 DP 方程,给出的就是斜率的形式,其中询问的点是确定的。此外发现各个点的横坐标是单调递增的,于是就可以用一个栈来维护凸包,之后二分查找凸包上可以让斜率最大的点。

三分什么的太麻烦了啊,二分好评。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 100005

int n;
long long d, a[N], dist[N], s[N], x[N], y[N];
double ans;
vector<int> v; vector<double> k;

double getk(int a, int b)
{
    return (double)(y[b] - y[a]) / (x[b] - x[a]);
}

inline long long read()
{
    long long x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n >> d;
    for (int i = 1; i <= n; ++i)
    {
        a[i] = read(); dist[i] = read(); s[i] = s[i - 1] + a[i];
        x[i] = i * d; y[i] = s[i - 1];
        while (!k.empty() && getk(i, v.back()) < k.back())
            v.pop_back(), k.pop_back();
        if (!v.empty()) k.push_back(getk(i, v.back()));
        v.push_back(i);
        x[0] = dist[i] + i * d; y[0] = s[i];
        int l = 0, r = k.size() - 1, t = v.size() - 1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (getk(v[mid], 0) > k[mid]) l = mid + 1;
            else r = mid - 1, t = mid;
        }
        ans += getk(v[t], 0);
    }
    cout << fixed << setprecision(0) << ans << endl;
    return 0;
}

BZOJ4172 弹珠 (hoodle)

问题描述

D.Ash 是一个喜欢玩弹珠的小男孩,他有一盒五颜六色的弹珠,在阳光的照射下非常美丽。

同样,他喜欢聆听弹珠相碰时的清脆声音。

经过他的观察,每个弹珠有三个参数 ai, pi, qi,均为正整数,分别为弹珠的碰撞损耗,发射损耗和发射能量。用弹珠 x 撞击弹珠 y,发出的声音响度为 B(x,y) = max{-ay*px+qx, 0}。

Ash 会把弹珠从弹珠盒中拿出来插入到现有弹珠序列中,或替换现有弹珠序列中已有的弹珠,Ash 会先告诉你操作的类型,“Insert”表示插入,“Change”表示替换。

Ash 的每个操作有两个参数 t,x。

若操作类型为“Insert”,表示把碰撞损耗为 x 的弹珠插入到当前序列第 t 个弹珠之后,t=0 表示将该弹珠插入到当前序列的第一个。

若操作类型为“Change”,表示把当前序列第 t 个弹珠之后的弹珠修改为碰撞损耗为 x 的弹珠,t=0 表示修改当前序列的第一个弹珠。

Ash 要玩这么一个游戏:

他先把第一颗弹珠放入袋中,然后从袋子中取出一颗弹珠撞击第二颗弹珠,

然后把第二颗弹珠收入袋中,然后从袋子中取出一颗弹珠撞击第三颗弹珠,

然后把第三颗弹珠收入袋中,然后从袋子中取出一颗弹珠撞击第四颗弹珠,

以此类推………

对于第 i 颗弹珠(i≠1),可以使用前 i-1 颗弹珠中的任何一颗来撞击它,并且每颗弹珠可以使用多次。

Ash 告诉你,经过他的摆放,保证当前序列中发射损耗和发射能量都是单调上升的。

他希望你能告诉他,对于第 2~n 颗弹珠中的每颗弹珠的最大撞击响度是多少。

输入格式

第 1 行,两个数,n,m。

第 2~m+1 行,每行一个字符串和两个数 t、x,表示操作。

第 m+2~m+1+n 行,每行两个数,分别为 pi 和 qi。

输出格式

输出 n-1 行,每行一个数,第 i 行表示第 i+1 弹珠的最大撞击响度。

样例输入

5 10
Insert 0 10
Change 0 2
Insert 0 2
Change 0 10
Insert 2 4
Insert 1 8
Change 1 2
Change 0 5
Insert 1 2
Change 1 4
1 5
2 10
3 14
4 17
5 19

样例输出

1
6
8
2

样例解释

第 1 次操作后,序列为{10}

第 2 次操作后,序列为{2}

第 3 次操作后,序列为{2,2}

第 4 次操作后,序列为{10,2}

第 5 次操作后,序列为{10,2,4}

第 6 次操作后,序列为{10,8,2,4}

第 7 次操作后,序列为{10,2,2,4}

第 8 次操作后,序列为{5,2,2,4}

第 9 次操作后,序列为{5,2,2,2,4}

第 10 次操作后,序列为{5,4,2,2,4}

对于第2颗弹珠,B(1,2)=1,最大值为 1。

对于第3颗弹珠,B(1,3)=3,B(2,3)=6,最大值为 6。

对于第4颗弹珠,B(1,4)=3,B(2,4)=6,B(3,4)=8,最大值为8。

对于第5颗弹珠,B(1,5)=1,B(2,5)=2,B(3,5)=2,B(4,5)=1,最大值为 2。

数据范围

对于前 30% 的数据,n <= 1000,m <= 3000,

对于前 50% 的数据,n <= 10000,m <= 20000,

对于 100% 的数据,n <= 400000,m <= 500000,0< ai, pi, qi <= 10^9。

数据是有梯度的。

吐槽

这道题出自 2015 年湖南省队集训题,在网上很难找到靠谱的题目描述。于是我在网上找到了一份残缺的题目描述之后整理了一下,贴到这里了。版权什么的,233。

题解

大半年了,写的第一个除 LCT 之外的 splay,真开心。

至于这道题呢,先求出来 a 数组(确定这不是两道题么?),然后斜率优化很显然啊。设 Xj=pj,Yj=qj,然后用栈维护一个上凸包,二分答案。

顺便测试了一下,deque 和 vector 的时间几乎是一样的。

  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
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>
using namespace std;

#define N 400005

struct splay_tree
{
    struct node
    {
        static node *nil;
        node *fa, *son[2];
        int size, val;

        node() : size(0), val(0) {}
        node(int _val) : size(1), val(_val)
        { fa = son[0] = son[1] = nil; }

        int check() { return fa->son[1] == this; }
        void combine(node *x, int d) { son[d] = x; x->fa = this; }
        void pushup() { size = son[0]->size + son[1]->size + 1; }
    };

    node *root;

    splay_tree()
    {
        root = new node(0);
        root->combine(new node(0), 1);
        root->pushup();
    }

    void rotate(node *x)
    {
        node *k = x->fa;
        int d = !x->check();
        k->combine(x->son[d], d ^ 1);
        k->fa->combine(x, k->check());
        x->combine(k, d);
        k->pushup(); x->pushup();
    }

    void splay(node *x, node *aim)
    {
        while (x->fa != aim)
        {
            if (x->fa->fa != aim)
                rotate(x->check() ^ x->fa->check() ? x : x->fa);
            rotate(x);
        }
        if (aim == node::nil) root = x;
    }

    node *find(node *x, int k)
    {
        if (k <= x->son[0]->size) return find(x->son[0], k);
        k -= x->son[0]->size;
        if (k == 1) return x;
        return find(x->son[1], k - 1);
    }

    void insert(int x, int y)
    {
        splay(find(root, x + 1), node::nil);
        splay(find(root, x + 2), root);
        root->son[1]->combine(new node(y), 0);
        root->son[1]->pushup(); root->pushup();
    }

    void change(int x, int y)
    {
        splay(find(root, x + 2), node::nil);
        root->val = y;
    }

    int *print(node *x, int *a)
    {
        if (x == node::nil) return a;
        a = print(x->son[0], a);
        *a = x->val;
        return print(x->son[1], a + 1);
    }
};

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == 'I') return 1;
        if (ch == 'C') return 2;
        if (ch == '-') f = -1; ch = getchar();
    }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

splay_tree::node *splay_tree::node::nil = new splay_tree::node();
splay_tree sp;
int n, m, a[N], p[N], q[N];
deque<int> v; deque<double> k;

double getk(int x, int y)
{
    return 1.0 * (q[x] - q[y]) / (p[x] - p[y]);
}

int main()
{
    cin >> n >> m;
    for (int opt, x, y, i = 1; i <= m; ++i)
    {
        opt = read(), x = read(), y = read();
        if (opt == 1)
            sp.insert(x, y);
        else
            sp.change(x, y);
    }
    sp.print(sp.root, &a[0]);
    for (int i = 1; i <= n; ++i)
        p[i] = read(), q[i] = read();
    v.push_back(1);
    for (int i = 2; i <= n; ++i)
    {
        int l = 0, r = k.size() - 1, ans = k.size();
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (k[mid] < a[i]) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        int t = v[ans];
        printf("%d\n", max(-1ll * a[i] * p[t] + q[t], 0ll));
        while (!k.empty() && getk(v.back(), i) > k.back())
            v.pop_back(), k.pop_back();
        if (!v.empty()) k.push_back(getk(v.back(), i));
        v.push_back(i);
    }
    return 0;
}