网站建设案例市场,网站的运营推广方案,点评类网站建设,no.7 wordpress[NOIP2017 普及组] 跳房子
题目背景
NOIP2017 普及组 T4
题目描述
跳房子#xff0c;也叫跳飞机#xff0c;是一种世界性的儿童游戏#xff0c;也是中国民间传统的体育游戏之一。
跳房子的游戏规则如下#xff1a;
在地面上确定一个起点#xff0c;然后在起点右侧画…[NOIP2017 普及组] 跳房子
题目背景
NOIP2017 普及组 T4
题目描述
跳房子也叫跳飞机是一种世界性的儿童游戏也是中国民间传统的体育游戏之一。
跳房子的游戏规则如下
在地面上确定一个起点然后在起点右侧画 n n n 个格子这些格子都在同一条直线上。每个格子内有一个数字整数表示到达这个 格子能得到的分数。玩家第一次从起点开始向右跳跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳依此类推。规则规定
玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏获得的分数为曾经到达过的格子中的数字之和。
现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷它每次向右弹跳的距离只能为固定的 d d d。小 R 希望改进他的机器人如果他花 g g g 个金币改进他的机器人那么他的机器人灵活性就能增加 g g g但是需要注意的是每 次弹跳的距离至少为 1 1 1。具体而言当 g d gd gd 时他的机器人每次可以选择向右弹跳的距离为 d − g , d − g 1 , d − g 2 , … , d g − 1 , d g d-g,d-g1,d-g2,\ldots,dg-1,dg d−g,d−g1,d−g2,…,dg−1,dg否则当 g ≥ d g \geq d g≥d 时他的机器人每次可以选择向右弹跳的距离为 1 , 2 , 3 , … , d g − 1 , d g 1,2,3,\ldots,dg-1,dg 1,2,3,…,dg−1,dg。
现在小 R 希望获得至少 k k k 分请问他至少要花多少金币来改造他的机器人。
输入格式
第一行三个正整数 n , d , k n,d,k n,d,k 分别表示格子的数目改进前机器人弹跳的固定距离以及希望至少获得的分数。相邻两个数 之间用一个空格隔开。
接下来 n n n 行每行两个整数 x i , s i x_i,s_i xi,si 分别表示起点到第 i i i 个格子的距离以及第 i i i 个格子的分数。两个数之间用一个空格隔开。保证 x i x_i xi 按递增顺序输入。
输出格式
共一行一个整数表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 k k k 分输出 − 1 -1 −1。
样例 #1
样例输入 #1
7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2样例输出 #1
2样例 #2
样例输入 #2
7 4 20
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2样例输出 #2
-1提示
输入输出样例 1 说明
花费 2 2 2 个金币改进后小 R 的机器人依次选择的向右弹跳的距离分别为 $ 2, 3, 5, 3, 4,3$先后到达的位置分别为 2 , 5 , 10 , 13 , 17 , 20 2, 5, 10, 13, 17, 20 2,5,10,13,17,20对应$ 1, 2, 3, 5, 6, 7$ 这 6 6 6 个格子。这些格子中的数字之和 $ 15$ 即为小 R 获得的分数。
输入输出样例 2 说明
由于样例中 7 7 7 个格子组合的最大可能数字之和只有 18 18 18所以无论如何都无法获得 20 20 20 分。
数据规模与约定
本题共 10 组测试数据每组数据等分。
对于全部的数据满足 1 ≤ n ≤ 5 × 1 0 5 1 \le n \le 5\times10^5 1≤n≤5×105 1 ≤ d ≤ 2 × 1 0 3 1 \le d \le2\times10^3 1≤d≤2×103 1 ≤ x i , k ≤ 1 0 9 1 \le x_i, k \le 10^9 1≤xi,k≤109 ∣ s i ∣ 1 0 5 |s_i| 10^5 ∣si∣105。
对于第 1 , 2 1, 2 1,2 组测试数据保证 n ≤ 10 n\le 10 n≤10。
对于第 3 , 4 , 5 3, 4, 5 3,4,5 组测试数据保证 n ≤ 500 n \le 500 n≤500。
对于第 6 , 7 , 8 6, 7, 8 6,7,8 组测试数据保证 d 1 d 1 d1。
分步分析
二分
我们可以看到我们应输出g假设 g 1 g_1 g1为正确答案即 g g 1 gg_1 gg1,可以取最大值,那么 g 1 1 g_11 g11也可以取最大值故对g可以二分答案检查是否有k分即可
检查
我们很容易得到一下程序
void solve(){int l0,rdis[n],ans-1;while(lr){int mid(lr)1;if (check(mid)) ansmid,rmid-1;else lmid1;}coutans;
}关键是怎么检查答案 我们设dp[i]是以第i个点结束的最大值我们发现具有无后效性可以dp我们求出二分出的g给定的跳跃区间进行dp即可
bool check(int g){int l0,r0;int mingmax(1,d-g),maxgdg;dp[0]0;for (int i1;in;i){dp[i]-1e6;while (rn and dis[i]-dis[r]ming) r;while(ln and dis[i]-dis[l]maxg) l;for (int jl;jr;j) dp[i]max(dp[i],dp[j]);dp[i]score[i];if (dp[i]k) return true;}return false;
}效率O( n 2 \text{n}^2 n2)不是很好 我们发现由于所有的dp值均来自于[l,r)故可以进行单调队列优化。(见代码)
代码
#includebits/stdc.h
using namespace std;
const int M1e6;
#define int long long
int dis[M],score[M],dp[M];
int n,d,k;
dequeint q;
bool check(int g){q.clear();int mingmax(1ll,d-g),maxgdg;for (int i0;in;i) dp[i]-1e18;dp[0]0;int las0; for(int i1;in;i){int lddis[i]-maxg,rddis[i]-ming;while(dis[las]ld) las;while(lddis[las] and dis[las]rd and lasi){while(!q.empty() and dp[q.back()]dp[las])q.pop_back();q.push_back(las);}while(!q.empty() and(dis[q.front()]ld)) q.pop_front();if (!q.empty()) dp[i]dp[q.front()]score[i];if (dp[i]k) return 1;}return false;
}
void read(){cinndk;for (int i1;in;i) cindis[i]score[i];
}
void solve(){int l0,rdis[n],ans-1;while(lr){int mid(lr)1;if (check(mid)) ansmid,rmid-1;else lmid1;}coutans;
}
signed main(){read();solve();return 0;
}分析
只看check
bool check(int g){q.clear();int mingmax(1ll,d-g),maxgdg;for (int i0;in;i) dp[i]-1e18;dp[0]0;int las0; for(int i1;in;i){int lddis[i]-maxg,rddis[i]-ming;while(dis[las]ld) las;while(lddis[las] and dis[las]rd and lasi){while(!q.empty() and dp[q.back()]dp[las])q.pop_back();q.push_back(las);}while(!q.empty() and(dis[q.front()]ld)) q.pop_front();if (!q.empty()) dp[i]dp[q.front()]score[i];if (dp[i]k) return 1;}return false;
}ming与maxg是所能移动距离的区间[ming,maxg]而ldrd是到达能到达i点的区间[ld,rd] 先选取第一个符合条件的点las即 d i s [ l a s ] ∈ [ l d , r d ] dis[las]\in[ld,rd] dis[las]∈[ld,rd]后每个点都尝试加入再选点时需要出队不符合条件的元素
