题解 P3957 【跳房子】
文飞扬
2018-04-29 19:50:18
这道题目是2017年普及组第四题，难度是比较大的，作为一名竞赛选手，碰到这样的难题，应该根据自己的知识情况，去尽可能获得更多的分数，下面一一分析，也可参见[跳房子（noip2017普及T4）解题报告](https://mp.weixin.qq.com/s?__biz=MzU1NDI3ODYyOQ==&mid=2247483695&idx=1&sn=2ff7893fbfb09f95c6bfd1e5287cc84a&chksm=fbe74aa5cc90c3b35be5c313a202bb3c5452b648080c967f80f6191b191992099d80d3bd02f2&mpshare=1&scene=1&srcid=0429nUL5wYwTum7DU2ngqcol&pass_ticket=FtBK%2FiCaxVJ6nyN53lG2yBFN0Go61WccqjAFJ2aAlLTngZ11HOe5GrYpWEk%2FdyWb#rd)。
1、假如我对于什么二分法，搜索，动态规划统统不知道，地地道道一个小白，那么，我也可以这么分析，如果所有格子中的正数之和低于所需分数，显然是不能到达的，那么直接输出-1，否则的话，我可设想，很可能需要把除了最后面分数为负的格子以外的所有格子都跳到（有点非完美算法的思想），因此，可以用如下伪代码实现；
```cpp
if（所有格子正数和小于所需分数）
输出-1；
else
求出从起点到最后一个正数格子的之间跳动的最小距离mind和最大距离maxd
输出d-mind和maxd-d之间较大的一个数
```
这样，应该能得一些分数。
2、求花多少金币来改造，显然，最少不花钱，最多呢就是一次能跳到最后一个格子距离的金币，而且花少量金币能完成的话，花更多金币也肯定能完成，这是一个很宽的范围，要从宽范围里面选择一个数字，毫无疑问，二分法是最快的，因此，程序的结构就是一个二分再加一个判断，结构如下。
```cpp
int main()
{
int i,ans=-1,l,r,m;
cin>>n>>d>>k;
for(i=1; i<=n; i++)
cin>>a[i][0]>>a[i][1];
l=0, r=a[n][0];
m=(l+r)/2;
while(l<=r)
{
if(check(m))//判断m是否符合要求
{
ans=m;
r=m-1;
}
else
{
l=m+1;
}
m=(l+r)/2;
}
cout<<ans;
return 0;
}
```
3、如何来判断某个金币数是否符合要求，怎么办？发现在能跳到的情况下，每个格子只有两种选择，要么跳到这个格子，要么不跳到这个格子，而且每个格子也可以越过一些格子跳到后面的一些格子去，因此跳到每个格子的分数有非常多的可能性，可用深度优先搜索来搜一下试试，然而，直接搜索的话，巨量的搜索树，肯定让程序挂掉，还是采取记忆化搜索方法，如果搜到这个格子发现以前搜过，而且分数比这次更高，那就直接返回，代码如下，可以得60分。
```cpp
int f[500005],a[500005][2],n,d,k,ok,lpos,rpos;
//i表示搜索第i格，pos目前位置，sum目前得分
void dfs(int i, int pos, int sum)
{
if(ok || i>n)
return;
if(a[i][0]-pos>rpos)//不能跳那么远
return;
if(a[i][0]-pos<lpos)//比最短跳远距离还短，跳下格
{
dfs(i+1,pos,sum);
return;
}
if(a[i][1]+sum>=k)
ok=1;
else if(a[i][1]+sum>f[i])
f[i]=a[i][1]+sum;
else
return;//以前搜索分数更高，直接返回
dfs(i+1, pos, sum);//不选 i号格子
dfs(i+1, a[i][0], sum+a[i][1]);//选择
}
bool check(int g)
{
ok=0;
lpos = d-g;
rpos = d+g;
if(lpos<=0)
lpos = 1;
memset(f,-127,sizeof(f));
dfs(1,0,0);
return ok;
}
```
4、想要得满分，那就只能动态规划了，设f[i]表示跳到第i格的最高得分，那么，f[i]肯定是从它前面那些能够跳到的格子里面得分最高的那个格子跳过来的，可以从i号格子前面第一个格子开始查找得分最高的格子，直到超过最大可跳范围为止，把这个区间的最大得分加上自己本身的分数就是第i格的最高分数了。另外，由于数据量巨大，开始搜索的右边值可以适当设小，这里设成了1005，设成10005也可以，这个程序可以满分。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long f[500005],a[500005][2],n,d,k,ok,lpos,rpos;
bool check(int g)
{
lpos = d-g;//跳的最短距离
rpos = d+g;//跳的最长距离
if(lpos<=0)
lpos = 1;
memset(f,-127,sizeof(f));//设为很小的负数
f[0]=0;
for(int i=1; i<=n; i++)
{
for(int j=i-1; j>=0; j--)
{
if(a[i][0]-a[j][0]<lpos) continue;
if(a[i][0]-a[j][0]>rpos) break;
f[i]=max(f[i],f[j]+a[i][1]);
if(f[i]>=k)
return 1;
}
}
return 0;
}
int main()
{
int i,ans=-1,l,r,m;
scanf("%lld%lld%lld",&n,&d,&k);
for(i=1; i<=n; i++)
scanf("%lld%lld",&a[i][0],&a[i][1]);
l=0, r=1005;
m=(l+r)/2;
while(l<=r)
{
if(check(m))
{
ans=m;
r=m-1;
}
else
{
l=m+1;
}
m=(l+r)/2;
}
cout<<ans;
return 0;
}
```
5、要想效率更高的话，考虑到f[i]总是从前面可跳区间的最大值跳过来，随着i往后面走，这个区间也往后面走，如果采用单调队列，速度会快很多，但是需要用到双端队列来构造单调队列，代码相对复杂一点，如下所示：
```cpp
bool check(int g)
{
lpos = d-g;//跳的最短距离
rpos = d+g;//跳的最长距离
if(lpos<=0)
lpos = 1;
memset(f,0,sizeof(f));
deque<int> dq;//定义一个双端队列
int cur=0;//当前待入队的格子编号
for(int i=1; i<=n; i++)
{
for(;cur<i&&a[i][0]-a[cur][0]>=lpos; cur++)
{
if(dq.empty())
dq.push_back(cur);
else
{
while(!dq.empty()&&f[cur]>=f[dq.back()])
dq.pop_back();
dq.push_back(cur);
}
}
while(!dq.empty()&&a[i][0]-a[dq.front()][0]>rpos)
dq.pop_front();
if(!dq.empty())
f[i]=f[dq.front()]+a[i][1];
else
f[i]=-999999999999;
if(f[i]>=k)
return 1;
}
return 0;
}
```
娄底一中刘文博 2018.4.29