现在的位置: 首页 > 综合 > 正文

线段树和单调队列优化DP—POJ2373解题报告 线段树和单调队列优化DP—POJ2373解题报告

2017年11月05日 ⁄ 综合 ⁄ 共 7455字 ⁄ 字号 小 中 大 ⁄ 评论关闭

线段树和单调队列优化DP---POJ2373解题报告

分类： 算法和数据结构 DP 线段树 单调队列2012-08-11
12:14 284人阅读 评论(0) 收藏 举报
优化querytreeinsert

Description

Farmer John's cows have discovered that the clover growing along the ridge of the hill in his field is particularly good. To keep the clover watered, Farmer John is installing water sprinklers along the ridge of the hill. 

To make installation easier, each sprinkler head must be installed along the ridge of the hill (which we can think of as a one-dimensional number line of length L (1 <= L <= 1,000,000); L is even). 

Each sprinkler waters the ground along the ridge for some distance in both directions. Each spray radius is an integer in the range A..B (1 <= A <= B <= 1000). Farmer John needs to water the entire ridge in a manner that covers each location on the ridge by
exactly one sprinkler head. Furthermore, FJ will not water past the end of the ridge in either direction. 

Each of Farmer John's N (1 <= N <= 1000) cows has a range of clover that she particularly likes (these ranges might overlap). The ranges are defined by a closed interval (S,E). Each of the cow's preferred ranges must be watered by a single sprinkler, which
might or might not spray beyond the given range. 

Find the minimum number of sprinklers required to water the entire ridge without overlap. 

Input

* Line 1: Two space-separated integers: N and L 

* Line 2: Two space-separated integers: A and B 

* Lines 3..N+2: Each line contains two integers, S and E (0 <= S < E <= L) specifying the start end location respectively of a range preferred by some cow. Locations are given as distance from the start of the ridge and so are in the range 0..L.

Output

* Line 1: The minimum number of sprinklers required. If it is not possible to design a sprinkler head configuration for Farmer John, output -1.

Sample Input

2 8
1 2
6 7
3 6

Sample Output

3

Hint

INPUT DETAILS: 

Two cows along a ridge of length 8. Sprinkler heads are available in integer spray radii in the range 1..2 (i.e., 1 or 2). One cow likes the range 3-6, and the other likes the range 6-7. 

OUTPUT DETAILS: 

Three sprinklers are required: one at 1 with spray distance 1, and one at 4 with spray distance 2, and one at 7 with spray distance 1. The second sprinkler waters all the clover of the range like by the second cow (3-6). The last sprinkler waters all the clover
of the range liked by the first cow (6-7). Here's a diagram:  

                 |-----c2----|-c1|       cows' preferred ranges

     |---1---|-------2-------|---3---|   sprinklers

     +---+---+---+---+---+---+---+---+

     0   1   2   3   4   5   6   7   8

The sprinklers are not considered to be overlapping at 2 and 6.

在长为L(<=1000000)的草地（可看成线段）上装喷水头，喷射是以这个喷水头为中心，喷水头的喷洒半径是可调节的，

调节范围为[a,b]。要求草地的每个点被且只被一个喷水头覆盖，并且有些连续区间必须被某一个喷水头覆盖，

而不能由多个喷头分段完全覆盖，求喷水头的最小数目。

很容易想到，这可以用dp解决，定义dp[i]为覆盖[0,i]区间所需的的最小喷头数，

则dp[0]=0,dp[i]=min{dp[i-2*b]....dp[i-2*a]}；因为喷头是向两边喷洒的，所以一个喷头覆盖的区间长度一定是偶数，

又由于题目要求喷头不能喷洒到[0,L]以外的区域，所以0开始的长度为奇数的子区间[0,L’]是不能被完全覆盖的。

还有一个问题是，某些连续区间必须被某一个喷水头覆盖这个限制该如何解决。我们可以这样想，

如果[s,e]这个区间只能被一个喷头覆盖，则[0,M](s<M<e)这一段子区间将不允许被完全覆盖，

因为如果[0,M]被完全覆盖会导致[s,e]区间被分割，所以我们可以对所以的[s,e]做上标记，

一种比较方便编码的方法是直接在dp这个数组上用一个特殊的值标记。我的做法是这样的：

[cpp] view
plaincopy

  1. dp[0]=0;  
  2. for(int i=1; i<=l; i++) dp[i]=inf;  
  3. for(int i=0; i<n; i++) {  
  4.         int s, e;    
  5.         scanf("%d%d", &s, &e);  
  6.         for(int j=s+1; j<e; j++) dp[j] = inf+1;//用inf+1表示不允许覆盖  
  7. }  

完整代码：

[cpp] view
plaincopy

  1. #include<cstdio>  
  2. #include<cstring>  
  3. #define L 1001000  
  4.   
  5. int a,b,n,l,inf,dp[L];  
  6.   
  7. int dpro(void)  
  8. {  
  9.      if(b<1) return -1;  
  10.      dp[0]=0;  
  11.                        
  12.      for(int i=2; i<=l; i+=2)  
  13.      {  
  14.          if (dp[i]<=inf) {  
  15.               int min = inf;  
  16.                 
  17.               for(int j=a; j<=b; j++) {  
  18.                     int idx = i-2*j;  
  19.                     if(idx<0) break;  
  20.                     if ( min>dp[idx] ) min=dp[idx];  
  21.               }  
  22.                 
  23.               dp[i]=min+1;  
  24.          }  
  25.      }  
  26.      if(dp[l]>=inf) return -1;  
  27.      else return dp[l];  
  28. }  
  29.   
  30. int main()  
  31. {  
  32.     while (scanf("%d%d", &n, &l)!=EOF) {  
  33.             
  34.           scanf("%d%d", &a, &b);  
  35.           inf = (l/a)+9;  
  36.           for(int i=0; i<=l; i++) dp[i]=inf;  
  37.             
  38.           for(int i=0; i<n; i++) {  
  39.                 int s, e;    
  40.                 scanf("%d%d", &s, &e);  
  41.                 for(int j=s+1; j<e; j++) dp[j] = inf+1;  
  42.           }  
  43.             
  44.           if(l&1==1) printf("-1\n");  
  45.           else printf("%d", dpro());  
  46.     }  
  47.     return 0;  
  48. }  

从上面的程序中我们看到，在最坏的情况下，时间复杂度是O(L^2)，而L的范围可达一百万，

所以在极端的数据下，这个程序是会超时的，所以我们需要对这个程序做一点优化。

在dp过程中的第二层for循环的作用是找出[i-2*b,i-2*a]这段区间的最小值，

这个查找一段区间的最小值的操作可以用线段树来优化，优化后的时间复杂度是O(LlgL)。

代码：

[cpp] view
plaincopy

  1. #include<cstdio>  
  2. #include<cstring>  
  3. #define L 1001000  
  4.   
  5. int a,b,n,l,inf,dp[L];  
  6. int tree[4*L];  
  7.   
  8. void updata(int *p, int rt, int l, int r,int pos, int k)  
  9. {  
  10.      if (l==r) {  
  11.           p[rt]=k;  
  12.           return ;  
  13.      }  
  14.      int mid=(l+r)>>1;  
  15.      if (pos<=mid) updata(p,rt<<1, l, mid, pos, k);  
  16.      else updata(p, rt<<1|1, mid+1, r, pos, k);  
  17.      int lv=p[rt<<1];  
  18.      int rv=p[rt<<1|1];  
  19.      p[rt]=lv<rv?lv:rv;  
  20. }  
  21.   
  22. int query(int *p,int rt, int l,int r, int s, int e)  
  23. {  
  24.     if(l==s && e==r) return p[rt];  
  25.     int mid = (l+r)>>1;  
  26.     if(e<=mid) return query(p, rt<<1, l, mid, s, e);  
  27.     if(s>mid) return query(p, rt<<1|1, mid+1, r, s, e);  
  28.     int lv=query(p,rt<<1, l, mid, s,mid);  
  29.     int rv=query(p,rt<<1|1, mid+1, r, mid+1, e);  
  30.     return lv<rv?lv:rv;  
  31. }  
  32.   
  33. int dpro(void)  
  34. {  
  35.      if(b<1) return -1;  
  36.      dp[0]=0;  
  37.   
  38.      for(int j=0; j<4*L; j++) tree[j]=L*2;  
  39.   
  40.      for(int j=a; j<=b; j++){  
  41.          if(dp[2*j]<=inf) dp[0+2*j] = dp[0]+1;  
  42.          updata(tree,1, 1, l ,j,dp[2*j]);  
  43.      }  
  44.        
  45.      for(int i=2*b+2; i<=l; i+=2)  
  46.      {  
  47.          int min;  
  48.          int pos = (i>>1);  
  49.          min = query(tree, 1, 1, l, pos-b, pos-a);  
  50.   
  51.          if (dp[i]<=inf) {  
  52.               //if(dp[i]>min+1)   
  53.               dp[i]=min+1;  
  54.               updata(tree,1,1,l,pos,dp[i]);  
  55.                      /*for(int j=a; j<=b; j++) { 
  56.                          int idx = i-2*j; 
  57.                          if(idx<0) break; 
  58.                          if ( dp[i]>dp[idx]+1 ) dp[i]=dp[idx]+1; 
  59.                      }*/  
  60.          }  
  61.      }  
  62.      if(dp[l]>=inf) return -1;  
  63.      else return dp[l];  
  64. }  
  65.   
  66. int main()  
  67. {  
  68.     while (scanf("%d%d", &n, &l)!=EOF) {  
  69.   
  70.           scanf("%d%d", &a, &b);  
  71.           inf = (l/a)+9;  
  72.           for(int i=0; i<=l; i++) dp[i]=inf;  
  73.   
  74.           for(int i=0; i<n; i++) {  
  75.                 int s, e;    
  76.                 scanf("%d%d", &s, &e);  
  77.                 for(int j=s+1; j<e; j++) dp[j] = inf+1;  
  78.           }  
  79.   
  80.           if(l&1==1) printf("-1\n");  
  81.           printf("%d\n", dpro());  
  82.     }  
  83.     return 0;  
  84. }  

另一种更好的优化方法是用单调队列优化：

代码：

[cpp] view
plaincopy

  1. #include<cstdio>  
  2. #define L 1001000  
  3.   
  4. int a,b,n,l,inf,dp[L],queue[L],head,tail,size;  
  5.   
  6. void insert(int idx)  
  7. {  
  8.      tail++;  
  9.      while(head<tail && dp[queue[tail-1]]>dp[idx]) tail--;  
  10.      queue[tail]=idx;  
  11.      while(idx-queue[head]>=size) head++;  
  12. }  
  13.   
  14. int dpro(void)  
  15. {  
  16.      if(b<1) return -1;  
  17.      dp[0]=0;  
  18.      size=2*b+1;  
  19.      head=0;  
  20.      tail=-1;  
  21.        
  22.      for(int i=a; i<=b; i++) if(dp[2*i]<=inf) dp[2*i]=1;       
  23.      int seg = 2*b-2*a;  
  24.      for(int i=0; i<=seg; i+=2) insert(i);  
  25.        
  26.      for(int i=2*b; i<=l; i+=2)  
  27.      {  
  28.          if(i-a*2>seg) insert(i-a*2);  
  29.          while(i-queue[head]>=size) head++;  
  30.          if (dp[i]<=inf) dp[i]=dp[queue[head]]+1;  
  31.      }  
  32.        
  33.      if(dp[l]>=inf) return -1;  
  34.      else return dp[l];  
  35. }  
  36.   
  37. int main()  
  38. {  
  39.     while (scanf("%d%d", &n, &l)!=EOF) {  
  40.             
  41.           scanf("%d%d", &a, &b);  
  42.           inf = (l/a)+9;  
  43.           for(int i=0; i<=l; i++) dp[i]=inf;  
  44.             
  45.           for(int i=0; i<n; i++) {  
  46.                 int s, e;    
  47.                 scanf("%d%d", &s, &e);  
  48.                 for(int j=s+1; j<e; j++) dp[j] = inf+1;  
  49.           }  
  50.             
  51.           if(l&1==1) printf("-1\n");  
  52.           else printf("%d\n", dpro());  
  53.     }  
  54.     return 0;  
  55. }  
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞