poj3171 Cleaning Shifts

这是一道数据结构优化dp的题

设区间的三个元素为 a, b, v.(左端点,右端点, 费用)。把右端点按递增排序,按顺序扫描贴纸。

设当前贴纸端点为 a, b.

那么可以写出方程 : f[ bi ] = min{ f[ x ] ( ai - 1 <= x < bi )} + ci;(不用修改整个区间)

初值 f[ M - 1 ] = 0, 其余为正无穷, 目标 min (f[ bi ] ( bi >= E) )

可以发现,方程式由区间的最小值转移过来,于是可以用线段树维护区间最小值。

最后注意起始端点的问题。如果你写线段树习惯1base,那么别忘了对读入数据做一些预处理(比如坐标统一  + 2)

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 const int MAXN = 10000 + 20;
 7 const int MAXE = 86399 + 20;
 8 const int INF = 0x3f3f3f3f;
 9 
10 int N, M, E;
11 
12 struct inv
13 {
14     int a, b, v;
15     inv(int a = 0, int b = 0, int v = 0) : a(a), b(b), v(v) {}
16     bool operator <(const inv &rhs) const{
17         return b < rhs.b;
18     }
19 }S[MAXN];
20 
21 int f[MAXE];
22 
23 namespace stree
24 {
25     #define ls (o << 1)
26     #define rs ((o << 1) | 1)
27     #define mid (((l) + (r)) >> 1)
28     int node[MAXE << 2];
29 
30     inline void pushup(int o)
31     {
32         node[o] = min(node[ls], node[rs]);
33     }
34 
35     void modify(int o, int l, int r, int p, int v)
36     {
37         if(l == r) return node[o] = v, void();
38         if(p <= mid) modify(ls, l, mid, p, v);
39         else modify(rs, mid + 1, r, p, v);
40         pushup(o); return ;
41     }
42 
43     int query(int o, int l, int r, int a, int b)
44     {
45         if(l > b || r < a) return INF;
46         if(a <= l && r <= b) return node[o];
47         return min(query(ls, l, mid, a, b), query(rs, mid + 1, r, a, b));
48     }
49 }
50 
51 int main()
52 {
53     //freopen("3171.txt", "r", stdin);
54     cin>>N>>M>>E; M += 2, E += 2;
55     for(int i = 1; i <= N; i++)
56     {
57         scanf("%d%d%d",&S[i].a, &S[i].b, &S[i].v);
58         S[i].a += 2, S[i].b += 2;
59     }    
60 
61     using namespace stree;
62     memset(node, INF, sizeof(node));
63     memset(f, 0x3f, sizeof(f));
64     f[M - 1] = 0;
65     modify(1, 1, MAXE, M - 1, 0);
66     sort(S + 1, S + N + 1);
67 
68     int ans = INF;
69     for(int i = 1; i <= N; i++)
70     {
71         if(S[i].b < M) continue;
72         int cur = query(1, 1, MAXE, S[i].a - 1, S[i].b) + S[i].v;
73         if(f[S[i].b] > cur)
74         {
75             f[S[i].b] = cur;
76             modify(1, 1, MAXE, S[i].b, f[S[i].b]);
77         }
78     }
79 
80     for(int i = E; i < MAXE; i++)
81         ans = min(ans, f[i]);
82     cout<<(ans == INF ? -1 : ans)<<endl;
83     return 0;
84 }
原文地址:https://www.cnblogs.com/wsmrxc/p/9020717.html