POJ2373...单调队列优化DP...

这道题调了我一天...呃.....开始很多地方没注意....传说中楼教主的男人八题搞定一道...

这道题是一道典型的DP题...但直接做时死超的....所以要用单调队列来优化....关于最基础的单调队列...我前一篇文章已经说了..所以直接分析本题..

题意是说有一个直线的山脊...喷泉是一个在中间向两边同时喷的...最近喷a..最远b...同时山脊上有牛...每只牛在一个区域里活动...牛活动的区域...只能被一个喷泉的水来覆盖...求最少的喷泉使山脊上所有地方都能有水浇灌到...

题意要注意 : 喷泉不能喷出去...比如山脊的长度是3..而我手上的喷泉能喷的距离是(2-3)...结果是-1...因为不论我喷泉在0-3的范围放哪里...都有水出去..这里算是Trick..

DP思想 :

f[k]代表0-k这块区域所需最少的喷泉.....注意.同样计算时要考虑到是正好喷到k!!..喷过k的要不得....

方程就出来了....f[ k ] =Min( f [ i ] ) + 1 其中 k-2*B <= i <= k-2*A ...并且 ( i + k ) %2==0 ( i,k同奇偶时..喷泉的水才能正好到k...).....

这里就是前面 i 个都放好了...然后再在 i - k中放一个使得这一段全被覆盖....应该好理解....

再一个考虑到有牛活动的区域只能有一个喷泉来覆盖.....首先将牛按 S优先...E次优先排序...k是从1-L扫描整个山脊的..用一个数g来记录当前到了第几个牛区域..g初始为1.当k在扫描过程中发现 k > cow[g]. S..也就是迈进了一个牛活动的区域...那么中间就不做了..k直接到cow[g].E去....这样就能保证牛活动区域只有一个喷泉了...

这个DP算法没一点问题....但是会超时...下面加入单调队列来优化...

单调队列优化:

从递归方程可以看出...每次更新k是要 k-2*B ~ k-2*A内...同奇偶最小的值.....有明显的单调思想..加入单调队列维护 k 之前数的单调性...当K<2*A..显然f[k]一直是没有办法设立喷泉...所以这一段都是-1...当k>=2*A了...则每次先将 k-2*B ~ k-2*A入队列...维护单调后...取直接取队首更新...这里如果每次都是放入k-2*B ~ k-2*A ..那单调队列就没有意义了...其实可以记录上一次已经放到那个数了...这一次接着上一次放就是的....比如用 m 记录上一次放到哪了...如果一段都是没牛的山脊...那每一次相当于只要放一个数去单调队列中...高效了很多....那为什么还要用个m来记录上一次放到哪了而不是不每次就是放一个数进去?这就是因为考虑进过有牛活动区域的问题...进过牛区域...每次的k就不知是++了...要跳过去一段长度了...所以不能只放一个了...

这里还有个问题...要保证 i 与 k 同奇偶...处理这个问题...我开始是更新玩单调队列后...再从前往后扫..扫到一个同奇偶的就停下来..用这个数更新...可以过...但很悬....1000MS..有种考试没几个...老师实在没办法加了几分正好60的感觉....于是着手优化....

为了保证奇偶...干脆就开两个队列...一个是偶数位的....一个是奇数位的...要加入队列的是偶数位的就加到偶数位的单调队列中去..是奇数位的就加到奇数位的单调队列里去..这样就省了一大段更新完队列再从前往后搜同奇偶的过程....

下面就是我优化的巨大成果！！ 快了快10倍被有木有！！！！

9227331	zzyzzy12	2373	Accepted	11920K	125MS	C++	1469B	2011-08-25 13:16:24
9227043	zzyzzy12	2373	Accepted	8000K	1000MS	C++	1580B	2011-08-25 11:50:53

Program :

#include<iostream>
#include<algorithm>
using namespace std;
#define oo 2000000000
struct pp
{
    int S,E;      
}cow[1001];
int N,L,A,B,Q[2][1000001],dp[1000001],k,g,h[2],p[2],m,x;
void UpdataQueue(int x,int k)
{    
     if (dp[k]!=-1)
     {
        if (p[x]<h[x] || dp[k]>dp[Q[x][p[x]]] )  { p[x]++; Q[x][p[x]]=k; }
        else
        {
          while (p[x]>=h[x] && dp[k]<dp[Q[x][p[x]]])  p[x]--; 
          p[x]++; Q[x][p[x]]=k;
        }
     }        
}
int GetAnswer()
{
     k=1; g=1; h[0]=h[1]=1; p[0]=p[1]=1; m=0;
     memset(dp,-1,sizeof(dp));
     memset(Q,0,sizeof(Q));
     dp[0]=0;
     while (k<=L)
     {
         if (g<=N && cow[g].S<k)
         {
             if (cow[g].E>k) k=cow[g].E;
             g++; 
             continue;     
         } 
         if (k<2*A) dp[k]=-1;
         else
         {
           x=k%2;  
           if (k-m>2*B) m=k-2*B;
           for (;m<=k-2*A;m++) UpdataQueue(m%2,m);           
           while (h[x]<=p[x] && k-Q[x][h[x]]>2*B ) h[x]++;        
           if (p[x]>=h[x]) dp[k]=dp[Q[x][h[x]]]+1;
         } 
         k++;         
     }
     return dp[L];     
}
bool cmp(pp a,pp b)
{
     if (a.S!=b.S) return a.S<b.S;
     return a.E<b.E;    
}
int main()
{  
     scanf("%d%d%d%d",&N,&L,&A,&B);
     for (int i=1;i<=N;i++) scanf("%d%d",&cow[i].S,&cow[i].E);
     sort(cow+1,cow+1+N,cmp);
     printf("%d\n",GetAnswer());
     return 0;   
}