Algoogle

Algorithm for Programming Contest

JOI 春合宿 2011 Bookshelf

Category: JOI Tag: dp, segment-tree

Bookshelf

問題概要


1からNまでの番号が振られた本がN冊適当にならんでいる.
今これを以下の操作で番号の昇順に直したい.
本を一冊選んで取り出す.
取り出された本を任意の位置に戻す.
この時コストがそれぞれA[i] (iは本の番号)かかるとき, 最小のコストを求めよ

解法


動かさない本のコストを最大化する.
始めの本の列を左から見ていく.
今見ている本の番号をiとし, iを動かさない時を考える.
iまでで動かさないコストの総和の最大は, iの始めの位置より左にあるもののうち, 番号がiより小さい一番右の本までで動かさないコストの総和の最大にiのコストを足したものになる.
これは始めの列の順でも昇順になっていたもの同士のため.
始めの列で位置関係が違う本同士では必ずどちらかが動く.

あとは一番右に来るのはiより前までのうちコストの総和の最大にもなるのでそれにiのコストを足せばiまでで動かさないコストの総和の最大が求まる.

コード


(bookshelf.cpp) download
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
#include <bits/stdc++.h>
using namespace std;
#define int long long

struct segtree  // RMQ
{
        int N;
        vector<int> dat;
        segtree(int n) {
                N = 1;
                while(N < n) N *= 2;
                dat.assign(2*N, 0);
        }
        // update k th element
        void update(int k, int a) {
                k += N-1; // leaf
                dat[k] = a;
                while(k > 0){
                        k = (k - 1) / 2;
                        dat[k] = max(dat[k*2+1], dat[k*2+2]);
                }
        }
        // min [a, b)
        int query(int a, int b){ return query(a, b, 0, 0, N);}
        int query(int a, int b, int k, int l, int r) {
                if(r <= a or b <= l) return 0;
                if(a <= l and r <= b) return dat[k];
                int m = (l + r) / 2;
                return max(query(a, b, k*2+1, l, m), query(a, b, k*2+2, m, r));
        }
};


int n, w[1<<17], sh[1<<17];

int solve()
{
        int ans = 0, sum = 0;
        segtree dp(n);
        for (int i = 0; i < n; i++) {
                sum += w[i]*2;
                sh[i]--;
                dp.update(sh[i], dp.query(0,sh[i])+w[sh[i]]*2);
                ans = max(ans, dp.query(sh[i],sh[i]+1));
        }
        return sum - ans;
}

void input()
{
        cin >> n;
        for (int i = 0; i < n; i++) cin >> w[i];
        for (int i = 0; i < n; i++) cin >> sh[i];

}

signed main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments