专业的建站公司推广,公司主页怎么填范本,织梦网站程序下载,博客网站做啥好正题
题目链接:http://poj.org/problem?id2373 题目大意
长度为L#xff0c;要求每个区域都被洒水器覆盖#xff0c;而且在每只奶牛的喜爱区域只能由一个洒水器覆盖#xff0c;洒水器必须放在整数点#xff0c;喷洒半径只能在a∼ba\sim ba∼b区间。 解题思路
我们考虑d…正题
题目链接:http://poj.org/problem?id2373 题目大意
长度为L要求每个区域都被洒水器覆盖而且在每只奶牛的喜爱区域只能由一个洒水器覆盖洒水器必须放在整数点喷洒半径只能在a∼ba\sim ba∼b区间。 解题思路
我们考虑dp我可以先想O(n2)O(n^2)O(n2)的。
fimin{fj}1(i−2b≤j≤i−2a)f_imin\{f_j\}1\ \ \ (i-2b≤j≤i-2a)fimin{fj}1 (i−2b≤j≤i−2a)
然后我们可以用单调队列维护一下区间。 然后我思考奶牛的问题奶牛所在的区间不可以有洒水器的中断而fif_ifi表示的是最后一个洒水器在iii位置中断需要的最少洒水器数量所以我们保证在奶牛喜爱的区域再往内一圈fif_ifi的值都为infinfinf就好了。 code
#includecstdio
#includealgorithm
#includecstring
#includequeue
#define inf 0x3f3f3f3f
using namespace std;
dequeint q;
int n,l,a,b,w[1000010],f[1000010],x,y,sum;
int main()
{scanf(%d%d%d%d,n,l,a,b);b2*b;a2*a;for(int i1;in;i){scanf(%d%d,x,y);w[x1];w[y]--;//标记}for(int i2;il;i2){sumw[i]w[i-1];//记录前缀和while(!q.empty()i-bq.front())q.pop_front();//维护区域int addni-a;//维护区域if(addn0){while(!q.empty()f[q.back()]f[addn])q.pop_back();//维护单调性q.push_back(addn);//加入队列}if(!q.empty()f[q.front()]inf!sum) f[i]f[q.front()]1;//有值else f[i]inf;//无值}printf(%d,f[l]inf?-1:f[l]);//输出
}
