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

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

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

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

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

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

DP思想 :

注意.同样计算时要考虑到是正好喷到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倍被有木有！！！！

Program :

#include#includeusing namespace std;#define oo 2000000000struct 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]dp[Q[x][p[x]]] ) { p[x]++; Q[x][p[x]]=k; } else { while (p[x]>=h[x] && dp[k]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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。