POJ3171 Cleaning Shifts DP，区间覆盖最值 - c++编程基础

TOP

POJ3171 Cleaning Shifts DP，区间覆盖最值

2015-07-20 17:58:46 来源: 作者: 【大中小】浏览:2次

题目大意，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 5000000001 long long BinTree[270000]; T cows[10001]; long long DP[86401]; template
              
                void Updateva lue(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; Updateva lue
                
                 (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); Updateva lue
                  
                   (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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ 2115 （模线性方程 -) 扩展欧..	下一篇：hdu2377Bus Pass(较为复杂的建图+..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: