题解 P3957 【跳房子】
NOIPOIER
2018-11-08 11:34:58
考场上看到这题是绝望的(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++