频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
线段树和单调队列优化DP---POJ2373解题报告
2012-08-12 08:01:00      个评论      
收藏   我要投稿

在长为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] 
dp[0]=0; 
for(int i=1; i<=l; i++) dp[i]=inf; 
for(int i=0; i<n; i++) { 
        int s, e;   
        scanf("%d%d", &s, &e); 
        for(int j=s+1; j<e; j++) dp[j] = inf+1;//用inf+1表示不允许覆盖 

完整代码:
[cpp]
#include<cstdio> 
#include<cstring> 
#define L 1001000 
 
int a,b,n,l,inf,dp[L]; 
 
int dpro(void) 

     if(b<1) return -1; 
     dp[0]=0; 
                      
     for(int i=2; i<=l; i+=2) 
     { 
         if (dp[i]<=inf) { 
              int min = inf; 
               
              for(int j=a; j<=b; j++) { 
                    int idx = i-2*j; 
                    if(idx<0) break; 
                    if ( min>dp[idx] ) min=dp[idx]; 
              } 
               
              dp[i]=min+1; 
         } 
     } 
     if(dp[l]>=inf) return -1; 
     else return dp[l]; 

 
int main() 

    while (scanf("%d%d", &n, &l)!=EOF) { 
           
          scanf("%d%d", &a, &b); 
          inf = (l/a)+9; 
          for(int i=0; i<=l; i++) dp[i]=inf; 
           
          for(int i=0; i<n; i++) { 
                int s, e;   
                scanf("%d%d", &s, &e); 
                for(int j=s+1; j<e; j++) dp[j] = inf+1; 
          } 
           
          if(l&1==1) printf("-1\n"); 
          else printf("%d", dpro()); 
    } 
    return 0; 


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

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

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

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


代码:

[cpp] 
#include<cstdio> 
#include<cstring> 
#define L 1001000 
 
int a,b,n,l,inf,dp[L]; 
int tree[4*L]; 
 
void updata(int *p, int rt, int l, int r,int pos, int k) 

     if (l==r) { 
          p[rt]=k; 
          return ; 
     } 
     int mid=(l+r)>>1; 
     if (pos<=mid) updata(p,rt<<1, l, mid, pos, k); 
     else updata(p, rt<<1|1, mid+1, r, pos, k); 
     int lv=p[rt<<1]; 
     int rv=p[rt<<1|1]; 
     p[rt]=lv<rv?lv:rv; 

 
int query(int *p,int rt, int l,int r, int s, int e) 

    if(l==s && e==r) return p[rt]; 
    int mid = (l+r)>>1; 
    if(e<=mid) return query(p, rt<<1, l, mid, s, e); 
    if(s>mid) return query(p, rt<<1|1, mid+1, r, s, e); 
    int lv=query(p,rt<<1, l, mid, s,mid); 
    int rv=query(p,rt<<1|1, mid+1, r, mid+1, e); 
    return lv<rv?lv:rv; 

 
int dpro(void) 

     if(b<1) return -1; 
     dp[0]=0; 
 
     for(int j=0; j<4*L; j++) tree[j]=L*2; 
 
     for(int j=a; j<=b; j++){ 
         if(dp[2*j]<=inf) dp[0+2*j] = dp[0]+1; 
         updata(tree,1, 1, l ,j,dp[2*j]); 
     } 
      
     for(int i=2*b+2; i<=l; i+=2) 
     { 
         int min; 
         int pos = (i>>1); 
         min = query(tree, 1, 1, l, pos-b, pos-a); 
 
         if (dp[i]<=inf) { 
              //if(dp[i]>min+1)  
              dp[i]=min+1; 
              updata(tree,1,1,l,pos,dp[i]); 
                     /*for(int j=a; j<=b; j++) {
                         int idx = i-2*j;
                         if(idx<0) break;
                         if ( dp[i]>dp[idx]+1 ) dp[i]=dp[idx]+1;
                     }*/ 
         } 
     } 
     if(dp[l]>=inf) return -1; 
     else return dp[l]; 

 
int main() 

    while (scanf("%d%d", &n, &l)!=EOF) { 
 
          scanf("%d%d", &a, &b); 
          inf = (l/a)+9; 
          for(int i=0; i<=l; i++) dp[i]=inf; 
 
          for(int i=0; i<n; i++) { 
                int s, e;   
                scanf("%d%d", &s, &e); 
                for(int j=s+1; j<e; j++) dp[j] = inf+1; 
          } 
 
          if(l&1==1) printf("-1\n"); 
          printf("%d\n", dpro()); 
    } 
    return 0; 

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


代码:

[cpp] 
#include<cstdio> 
#define L 1001000 
 
int a,b,n,l,inf,dp[L],queue[L],head,tail,size; 
 
void insert(int idx) 

     tail++; 
     while(head<tail && dp[queue[tail-1]]>dp[idx]) tail--; 
     queue[tail]=idx; 
     while(idx-queue[head]>=size) head++; 

 
int dpro(void) 

     if(b<1) return -1; 
     dp[0]=0; 
     size=2*b+1; 
     head=0; 
     tail=-1; 
      
     for(int i=a; i<=b; i++) if(dp[2*i]<=inf) dp[2*i]=1;      
     int seg = 2*b-2*a; 
     for(int i=0; i<=seg; i+=2) insert(i); 
      
     for(int i=2*b; i<=l; i+=2) 
     { 
         if(i-a*2>seg) insert(i-a*2); 
         while(i-queue[head]>=size) head++; 
         if (dp[i]<=inf) dp[i]=dp[queue[head]]+1; 
     } 
      
     if(dp[l]>=inf) return -1; 
     else return dp[l]; 

 
int main() 

    while (scanf("%d%d", &n, &l)!=EOF) { 
           
          scanf("%d%d", &a, &b); 
          inf = (l/a)+9; 
          for(int i=0; i<=l; i++) dp[i]=inf; 
           
          for(int i=0; i<n; i++) { 
                int s, e;   
                scanf("%d%d", &s, &e); 
                for(int j=s+1; j<e; j++) dp[j] = inf+1; 
          } 
           
          if(l&1==1) printf("-1\n"); 
          else printf("%d\n", dpro()); 
    } 
    return 0; 

作者:sunny606
点击复制链接 与好友分享!回本站首页
相关TAG标签 线段 队列 报告
上一篇:HDOJ 3537 Daizhenyang's Coin (翻硬币游戏)
下一篇:poj 1699 TSP(状态压缩DP) + KMP
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站