题解 P3957 【跳房子】

NOIPOIER

2018-11-08 11:34:58

Solution

考场上看到这题是绝望的(T_T) 连O(2^n)的深搜都炸了…… 还好今年不考普及组了(貌似提高更……) 再看一眼数据范围 对于第 1, 2 1,2组测试数据, n ≤ 10; 对于第 3, 4, 53,4,5 组测试数据, n ≤ 500 对于第 6, 7, 86,7,8 组测试数据, d = 1 对于全部的数据满足1 ≤ n ≤ 500000, 1 ≤ d ≤2000, 1 ≤ x_i, k ≤ 10^9, |s_i| < 10^5 我们循序渐进 M1 0(骗分,最理所当然的想法) 直接输出-1,然而CFF呵呵,没有-1; M2 20 看似就像是比较好大的,然而 我就死在了这上面。 具体思路dfs枚举取或不取 比较答案与k的大小 然后就有20分了 (考场上太弱,dfs都没打完) M3 80(开始变的玄学……) 首先,不(hen)难看出,答案有单调性…… 对于一个 g 机器人蹦跶的范围【max(0,d-g),d+g】 显然 g越大 机器人会蹦跶的越欢…… 于是,就有常用方法——二分答案的诞生了 while(l!=r){ long long mid=(l+r)/2; if(check(mid))r=mid; else l=mid+1; } if(!check(l)){ printf("-1"); return 0; } else printf("%lld",l); 没错,就长这样,整个程序的————关键落在了 check上。 如何check?想(kan)一(ti)想(jie)就会发现dp 这显然是一个最优化问题, 设dp【i】为跳到第i个点时机器人最大得分 初始时,dp【i】=-inf;dp【0】=0; —————————————————————————— 转移: 显然 dp【i】=dp【j】+val【i】; (val【i】为第i个点的得分) j显然是有条件的 还记的蹦跶的范围吗? 【max(0,d-g),d+g】 pos【j】应该在【pos【i】-d-g,pos【i】-max(0,d-g)】之间 pos【i】表示第i个点的位置 所以我们就有了核心代码———————————— bool check(long long mid){ long long l=max(0,d-mid); long long r=d+mid; for(int i=1;i<=n;i++) { for(int j=0;j<i;j++) if(pos[j]<=pos[i]-l&&pos[j]>=pos[i]-r) dp[i]=max(dp[i],dp[j]+val[i]); if(dp[i]>=k)return 1; } return 0; } 复杂度O(n^2*logSmax) 好像很快的样子? 500000的数据量可不是吃素的…… 洛谷上都不支持下载了…… 1min都跑不完…… 非常令人绝望…… 于是再想(kan)一(ti)想(jie) 就有了M4 100 出锅出在哪?二分同学已经很优秀了,而dp同学却颓得不像样 我们得优化它 M4 100 正解 二分答案+dp+单调队列优化 O(nlogSmax) 终极玄学—————————— 我们还得在check函数上做手脚 dp【i】=dp【j】+val【i】; 再看一眼状态转移方程 惊奇的发现dp【i】只与dp【j】有关 OI界两个神器,便派上了用场 当dp【i】只与j有关,我们可以使用—————— 单调队列(还有一个叫斜率优化,虽然用不到) 假设Q里面front是最优状态 则dp【i】=dp【Q.front()】+val【i】; 瞬间降维,唯一的问题就是维护Q了 首先,每一个状态(即i)只会进出一次 题目要求在区间【pos【i】-d-g,pos【i】-max(0,d-g)】 内求解,显然,太老的得弹出去,太年轻的不让进 while(Q.size()&&(pos[Q.front()])<pos[i]-r) Q.pop_front();//已经超出了下界pos【i】-r las为最远的待加入的编号 while(pos[las]<pos[i]-r)las++;//还没被加入,就已经出范围了 while(pos[i]-l>=pos[las]&&pos[i]-r<=pos[las]&&las<i) {//保证比上界小 while(Q.size()&&(dp[Q.back()]<=dp[las] ||pos[Q.back()]<pos[i]-r)) //如果值没有当前的大,显然的出队 //即使值大,不在范围内,也出队 Q.pop_back(); Q.push_back(las); las++; } 可以证明每一个点只进出一次 成功降维 O(n*logSmax) 全部代码 #include<bits/stdc++.h> using namespace std; const long long inf=1e18; int n; long long d,k; long long pos[500001],val[500001]; long long dp[500001]; deque<long long> Q; bool check(long long mid){ if(!Q.empty())Q.clear(); long long l=(d-mid<0?0:d-mid); long long r=d+mid; int las=0; for(int i=0;i<=n;i++) dp[i]=-inf; dp[0]=0; for(int i=1;i<=n;i++) { while(pos[las]<pos[i]-r)las++; while(pos[i]-l>=pos[las]&&pos[i]-r<=pos[las]&&las<i) { while(Q.size()&&(dp[Q.back()]<=dp[las]||pos[Q.back()] <pos[i]-r)) Q.pop_back(); Q.push_back(las); las++; } while(Q.size()&&(pos[Q.front()])<pos[i]-r) Q.pop_front(); if(Q.size()!=0)dp[i]=dp[Q.front()]+val[i]; if(dp[i]>=k)return 1; } return 0; } int main(){ scanf("%d%lld%lld",&n,&d,&k); for(int i=1;i<=n;i++) scanf("%lld%lld",&pos[i],&val[i]); long long l=0,r=pos[n]; while(l!=r){ long long mid=(l+r)/2; if(check(mid))r=mid; else l=mid+1; } if(!check(l)){ printf("-1"); return 0; } else printf("%lld",l); return 0; } 如果你仍然出锅了 !!!! 1: long long是必须的 2:inf得足够大,0x7f7f7f7f太小了 3:取max时,你会发现max(0,d-mid)会CE 因为 0:int d-mid:long long 还是 if语句或?:运算符更安全 4:二分时注意l和r 应该没了吧。 NOIP2018rp++