Algoogle

Algorithm for Programming Contest

PKU 3171 Cleaning Shifts

Category: PKU Tag: segment-tree

Cleaning Shifts

問題概要


[M, E]の時間全てをカバーするように牛を働かせるとき, コストの最小を求めよ.
牛は働く時間[Si, Ti]とそのときのコストViがそれぞれ決まっている.
全てカバーできない時は-1を出力する.

解法


DP
とりあえず閉区間きもちわるいのですべて半開区間に直す(好みの問題, ついでに全部からM引く). 各牛について, 開始時刻が早い順に
dp[i] := 時刻iまで掃除させるときの最小コスト
更新式は以下のようになる.

1
2
3
for i in [0, N)
    for j in [Si, Ti)
        dp[Ti] = min(dp[Ti], dp[j] + Vi)

しかしこれでは明らかにTLE.
jについてのfor文をみると, [Si, Ti) のdp配列の最小値を持ってくればfor文回さなくても更新できることがわかる.
よってdp配列をSegment Treeで実装すれば全体の計算量はO(N log E)になって嬉しい.
あとコストの最大がNSぐらいになってintだとやばそうなのでlong longにした.

コード


(3171.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
#include <algorithm>
#include <cstdio>

#define int long long
using namespace std;

struct cow{
    int s, t, v;
    cow(){}
    cow(int s, int t, int v):s(s),t(t),v(v){}
    bool operator<(const cow &c)const{ return s < c.s;}
};

const int inf = 1e16;
int N, M, E, MA;
cow C[10010];

struct ST{
    int dp[300010];
    ST(){
        for(int i = 0; i < 2*MA-1; i++)
            dp[i] = inf;
    }
    void update(int k, int val){
        k += MA-1;
        dp[k] = val;
        while(k > 0){
            k = (k-1) / 2;
            dp[k] = min(dp[2*k+1], dp[2*k+2]);
        }
    }
    int query(int a, int b){ return query(a, b, 0, 0, MA);}
    int query(int a, int b, int k, int l, int r){
        if(a >= r or b <= l) return inf;
        if(a <= l and r <= b) return dp[k];
        int m = (l + r) / 2;
        return min(query(a,b,2*k+1,l,m), query(a,b,2*k+2,m,r));
    }
};

signed main(){
    scanf("%lld%lld%lld", &N, &M, &E);
    E -= M-1;
    for(int i = 0; i < N; i++){
        int s, t, v; scanf("%lld%lld%lld", &s, &t, &v);
        C[i] = cow(s-M, t-M+1, v);
    }
    //    printf("%lld %lld %lld\n", N, M, E);
    sort(C, C+N);
    MA = 1LL;
    while(E > MA) MA <<= 1LL;
    ST st = ST();
    st.update(0,0);
    for(int i = 0; i < N; i++)
        st.update(C[i].t, min(st.dp[C[i].t+MA-1], st.query(C[i].s, C[i].t) + C[i].v));

    int ans = st.dp[E+MA-1];
    if(ans == inf) ans = -1;
    printf("%lld\n", ans);
    return 0;
}

Comments