POJ3171 Cleaning Shifts DP，区间覆盖最值-白红宇

POJ3171 Cleaning Shifts DP，区间覆盖最值

阅读量：5061 次

发布时间：2019-06-12

本文共 2361 字，大约阅读时间需要 7 分钟。

题目大意。N个区间覆盖[T1,T2]及相应的代价S，求从区间M到E的所有覆盖的最小代价是多少。

(1 <= N <= 10,000)。(0 <= M <= E <= 86,399).

思路是DP,首先将每一个区间依照T2从小到大排序，设dp(k)为从m覆盖到k所需最小代价，则有

dp(T2[i]) = min(dp(T2[i]), {dp(j) + Si, T1[i] - 1<=j <= T2[i]}),对于 {dp(j) + Si, T1[i] - 1<=j <= T2[i]}我们能够用线段树来进行优化，所以终于复杂度为O(n*logE)。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 using namespace std;struct T{ int t1; int t2; int S;};#define MAXV 5000000001long long BinTree[270000];T cows[10001];long long DP[86401];template
                 
                  void UpdateValue(TYPE st[],int i, TYPE value, int N, bool bMin){ i += N - 1; st[i] = value; while (i > 0) { i = (i - 1) / 2; if (bMin) { st[i] = min(st[i * 2 + 1], st[i * 2 + 2]); } else st[i] = max(st[i * 2 + 1], st[i * 2 + 2]); }}template
                  
                   TYPE QueryST(TYPE st[], int a, int b, int l, int r, int k, bool bMin){ if (l > b || a > r) { return bMin ? MAXV : 0; } if (l >= a && b >= r) { return st[k]; } else { TYPE value1 = QueryST(st, a, b, l, (r + l) / 2, k * 2 + 1, bMin); TYPE value2 = QueryST(st, a, b, (r + l) / 2 + 1, r, k * 2 + 2, bMin); if (bMin) { return min(value1, value2); } else { return max(value1, value2); } }}int compT(const void* a1, const void* a2){ if (((T*)a1)->t2 - ((T*)a2)->t2 == 0) { return ((T*)a1)->t1 - ((T*)a2)->t1; } else return ((T*)a1)->t2 - ((T*)a2)->t2;}int main(){#ifdef _DEBUG freopen("e:\\in.txt", "r", stdin);#endif int N, M, E; scanf("%d %d %d", &N, &M, &E); M++; E++; for (int i = 0; i < N; i++) { scanf("%d %d %d", &cows[i].t1, &cows[i].t2, &cows[i].S); cows[i].t1++; cows[i].t2++; } int maxe = 1; while (maxe < E) { maxe *= 2; } for (int i = 0; i < maxe * 2;i++) { BinTree[i] = MAXV; } for (int i = 0; i <= E;i++) { DP[i] = MAXV; } DP[M - 1] = 0; UpdateValue
                   
                    (BinTree, M - 1, 0, maxe, true); qsort(cows, N, sizeof(T), compT); for (int i = 0; i < N;i++) { DP[cows[i].t2] = min(DP[cows[i].t2], QueryST
                    
                     (BinTree, cows[i].t1 - 1, cows[i].t2, 0, maxe - 1, 0, true) + cows[i].S); UpdateValue
                     
                      (BinTree, cows[i].t2, DP[cows[i].t2], maxe, true); } if (E <= cows[N - 1].t2) { DP[E] = QueryST
                      
                       (BinTree, E, cows[N - 1].t2, 0, maxe - 1, 0, true); } if (DP[E] >= MAXV) { printf("-1\n"); } else printf("%I64d\n", DP[E]); return 0;}