http://acm.hust.edu.cn/vjudge/problem/16596
/* solution: 单调队列优化dp 首先定义状态：f[i]表示恰好覆盖到i时，用了多少喷头。其次定义状态转移方程： 可以很容易看出当A<=j-i<=B时（A，B均为直径），f[j]=min(f[i])+1。但是 A和B之间最多可以相差1998,所以若是枚举的话肯定超时！所以可以考虑用队列来 进行优化。在求j时将满足j-B<=i<=j-A的i点压进去。每次要求j时就将队头元素 取出，若是小于j-B，说明是求解上一步循环所压入的点，对这次求解无用，抛弃之。 但千万要保证在队列内的所有点不能超过j-A！求出f[j]后记得将下一步求解所需要 的初始值,f[j-B+2]压入。 另外还有一些细节处理。因为由于直径等于半径2倍的关系，所以在求解过程中之考虑 偶数点，可以先做判断，l如果是奇数就直接无解。 题目还要求一头奶牛活动范围必须在一个喷头内。所以对给出的闭区间，除了首尾两端 中间所有点都不能求解。可以用一个bool数组来表示。 note: 记住定义的是小顶堆啊！ 题目hint给出的示意图有毒！是错误的！！WA了半天！闭区间两端是点的位置。 date: 2016/8/15 */ #include <iostream> #include <cstdio> #include <queue> #include <cstring> using namespace std; const int maxn = 1000 + 5; const int maxl = 1000000; const int INF = 1 << 30; struct Node { int x, fx; Node(int x, int fx) : x(x), fx(fx) {} Node() {} bool operator < (const Node& rhs) const { return fx > rhs.fx; //记住定义小顶堆 } }; int n, l; //奶牛以及道路的长度 int A, B, s, e; //喷泉的喷洒半径以及每头奶牛的活动范围 bool cowThere[maxl]; int f[maxl]; //f[i]表示恰好覆盖长度为i时候的所用喷头 int main() { //freopen("input.txt", "r", stdin); while(~scanf("%d%d", &n, &l)) { if(l % 2 != 0) printf("-1\n"); else { scanf("%d%d", &A, &B); memset(cowThere, 0, sizeof(cowThere)); for(int i = 0; i < n; i++) { scanf("%d%d", &s, &e); for(int j = s+1; j < e; j++) //hint插图误导人！ cowThere[j] = true; //奶牛活动范围给出的描述是个闭区间，首尾两个数值是点。 } A *= 2; B *= 2; // for(int i = 0; i <= l; i++) printf("%d ", cowThere[i]); printf("\n"); for(int i = 0; i <= l; i++) f[i] = INF; priority_queue<Node> pq; for(int i = A; i <= B; i += 2) { if(!cowThere[i]) { f[i] = 1; if(i <= B+2-A) { pq.push(Node(i, 1)); //printf("push %d\n", i); } } } //动规边界初始化 for(int i = B + 2; i <= l; i += 2) { if(!cowThere[i]) { //cout << "#" << endl; Node u; while(!pq.empty()) { //这个循环会筛选出求i是需要的范围内的点 u = pq.top(); //cout << u.x << endl; if(u.x < i-B) pq.pop(); else break; } if(!pq.empty()) { f[i] = u.fx + 1; } } if(f[i-A+2] != INF) pq.push(Node(i-A+2, f[i-A+2])); //将下一个点压入，为进一步求解做准备 } if(f[l] == INF) printf("-1\n"); else printf("%d\n", f[l]); } } return 0; }