跳房子（弱化版）

题目描述

跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。

跳房子的游戏规则如下：

在地面上确定一个起点，然后在起点右侧画 n 个格子，这些格子都在同一条直线上。每个格子内有一个数字（整数），表示到达这个 格子能得到的分数。玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。规则规定：

玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。

现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷，它每次向右弹跳的距离只能为固定的 d。小 R 希望改进他的机器人，如果他花 g 个金币改进他的机器人，那么他的机器人灵活性就能增加 g，但是需要注意的是，每 次弹跳的距离至少为 11。具体而言，当 g<dg<d 时，他的机器人每次可以选择向右弹跳的距离为 d−g,d−g+1,d−g+2,…,d+g−1,d+gd−g,d−g+1,d−g+2,…,d+g−1,d+g；否则当 g≥dg≥d 时，他的机器人每次可以选择向右弹跳的距离为 1,2,3,…,d+g−1,d+g1,2,3,…,d+g−1,d+g。

现在小 R 希望获得至少 k 分，请问他至少要花多少金币来改造他的机器人。

输入格式

第一行三个正整数 n,d,k 分别表示格子的数目，改进前机器人弹跳的固定距离，以及希望至少获得的分数。相邻两个数 之间用一个空格隔开。

接下来 n 行，每行两个整数 xi,si 分别表示起点到第 i 个格子的距离以及第 i个格子的分数。两个数之间用一个空格隔开。保证 xi 按递增顺序输入。

输出格式

共一行，一个整数，表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 k 分，输出 −1。

输入格式

第一行三个正整数 n,d,k 分别表示格子的数目，改进前机器人弹跳的固定距离，以及希望至少获得的分数。相邻两个数 之间用一个空格隔开。

接下来 n 行，每行两个整数 xi,si 分别表示起点到第 i个格子的距离以及第 i个格子的分数。两个数之间用一个空格隔开。保证 xi 按递增顺序输入。

输出格式

共一行，一个整数，表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 k 分，输出 −1 。

输入输出样例

输入 #1复制

7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

输出 #1复制

2

输入 #2复制

7 4 20
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

输出 #2复制

-1

说明/提示

样例 1 说明

花费 22 个金币改进后，小 R 的机器人依次选择的向右弹跳的距离分别为 2,3,5,3,4,32,3,5,3,4,3，先后到达的位置分别为 2,5,10,13,17,202,5,10,13,17,20，对应 1,2,3,5,6,71,2,3,5,6,7 这 66 个格子。这些格子中的数字之和 1515 即为小 R 获得的分数。

样例 2 说明

由于样例中 77 个格子组合的最大可能数字之和只有 1818，所以无论如何都无法获得 2020 分。

数据规模与约定

对于全部的数据满足 1≤n≤5001≤n≤500，1≤d≤2×1031≤d≤2×103，1≤xi,k≤1091≤xi​,k≤109，∣si∣<105∣si​∣<105。

---------------------------------------------------------------------------------------------------------------------------------

分析与解答：

A-G分别表示1号到7号格子，红色文字表示该格子对应的分值。

初始状态，当d = 4时，无法由起点跳到其它点，此时需要花费2金币改造，改造后机器人的移动范围变为[2,6]，此时：
1. 机器人跳到A点，得6分，总分6分
2. 机器人跳到B点，得-3分，总分3分
3. 机器人跳到C点，得3分，总分6分
4. 机器人跳到E点，得1分，总分7分
5. 机器人跳到F点，得6分，总分13分

所以，当花费2金币进行改造时，得分不低于10分。

解答1： 

算法思想(二分搜索+动态规划)
假设已求得了最优解，即花费g 
个金币进行改造后，得分不低于k 
。如果在此状态下再花费若干金币，那么得分一定不低于k 
。因此花费的金币数和得分之间满足单调性质，是一个单调递增关系（不一定是严格单调递增），可以使用二分求解在花费不同金币进行改造时得分是否满足条件。
要求花费g 
个金币进行改造后的最高得分，可以使用动态规划的思想：
状态表示： f[i]表示在花费g个金币进行改造后，跳过前i个格子得到的最高得分
状态转移：f[i] = max{f[j] + w[i]}，其中max(1,d−g)≤dist[i]−dist[j]≤d+g 

注：w[i]为i个格子的得分
时间复杂度 O(n×d×logxn) ，需要对DP进行剪枝。 

#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
int n,d,k;
int a[500010][2];
ll f[500010],sum=0;
bool check(int g) {cout<<"g="<<g<<' '<<endl;int l=max(1,d-g),r=d+g;cout<<"%%%"<<l<<' '<<r<<endl;memset(f,-127,sizeof f);f[0]=0;for(int i=1; i<=n; i++) {//每个格子int td;for(int j=0; j<i; j++) {//当前格子的前面格子,从小到大去寻找td=a[i][0]-a[j][0];cout<<"格子***"<<j<<" ，格子举例"<<td<<endl;if(td>=l&&td<=r) {// f[i]积分，当前i格子的分数f[i]=max(f[i],f[j]+a[i][1]);}if(f[i]>=k) return true;if(td<l) break;}cout<<i<<' '<<f[i]<<endl;}return false;
}int main() {scanf("%d %d %d",&n,&d,&k);for(int i=1; i<=n; i++) {scanf("%d %d",&a[i][0],&a[i][1]);if(a[i][1]>0) {cout << "a[" << i << "][1]" << endl;sum += a[i][1];cout << "sum = " << sum << endl;}}if(sum<k) {//所有的正分加起来都不够希望获得的分数printf("-1");return 0;}//二分int l=0,r=max(0,a[n][0]-d);cout << "a[" << n-1 << "][0]=" << a[n][0] << endl;cout << "d = " << d << endl;while(l<r) {cout<<'*'<<l<<' '<<r<<endl;int mid=(l+r)/2;if(check(mid)) r=mid;else l=mid+1;}printf("%lld",l);return 0;
}

解答2：基本思想

要解决这个问题，我们需要动态规划（Dynamic Programming，DP）的思想。我们要确定最少需要花费多少金币来改造机器人，使其能够获得至少 k 分。以下是详细的步骤和思路：

1. ‌输入处理‌：

   • 读取 n, d, k。
   • 读取每个格子的位置和分数。

2. ‌确定DP状态‌：

   • dp[i][j] 表示花费 j 个金币时，到达第 i 个格子能获得的最大分数。

3. ‌状态转移‌：

   • 对于每个格子 i 和每个花费 j，我们需要尝试所有可能的跳跃距离，并更新 dp[i][j]。
   • 跳跃距离的范围根据 g 和 d 的关系分为两种情况：
     • 当 g < d 时，跳跃距离范围是 [d-g, d+g]。
     • 当 g >= d 时，跳跃距离范围是 [1, d+g]。

4. ‌初始化‌：

   • 起点位置特殊处理，dp[j] 初始化为 0（起点没有分数，但是可以作为跳跃的出发点）。

5. ‌结果计算‌：

   • 遍历所有格子和所有花费，计算能得到的最大分数。
   • 最终找到最小的花费 j 使得在某个格子上的分数大于等于 k。

6. ‌边界情况处理‌：

   • 如果无法获得至少 k 分，返回 -1。

以下是实现该算法的C++代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>using namespace std;struct Grid {int position;int score;
};int main() {int n, d, k;cin >> n >> d >> k;vector<Grid> grids(n);for (int i = 0; i < n; ++i) {cin >> grids[i].position >> grids[i].score;}// 由于位置是按递增顺序输入的，我们可以直接使用下标来访问格子vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1)); // n+1 个格子, 最多花费 n 个金币（松弛上界）dp = 0; // 在起点，不花费金币，得分为 0for (int g = 0; g <= n; ++g) { // 金币花费从 0 到 nfor (int i = 0; i < n; ++i) { // 遍历每一个格子if (dp[i][g] == -1) continue; // 如果当前状态不可达，跳过int minJump = max(1, d - g);int maxJump = d + g;for (int jump = minJump; jump <= maxJump; ++jump) {// 查找下一个可达的格子for (int next = i + 1; next <= n; ++next) {if (grids[next - 1].position - grids[i].position > jump) break;if (grids[next - 1].position - grids[i].position == jump) {dp[next][g] = max(dp[next][g], dp[i][g] + grids[next - 1].score);}}}}}int minCoins = INT_MAX;for (int g = 0; g <= n; ++g) {for (int i = 0; i <= n; ++i) {if (dp[i][g] >= k) {minCoins = min(minCoins, g);}}}if (minCoins == INT_MAX) {cout << -1 << endl;} else {cout << minCoins << endl;}return 0;
}

解释

• ‌初始化‌：dp = 0，其他均为 -1，因为初始时其他状态都是不可达的。
• ‌状态转移‌：通过遍历每一个格子和每一种花费，尝试所有可能的跳跃距离，更新 dp 数组。
• ‌结果计算‌：找到最小的花费 g 使得在某个格子上的分数大于等于 k。

该算法的时间复杂度为 O(n3)，在合理的数据范围内是可以接受的。

---------------------------------------------------------------------------------------------------------------------------------

解答3： 

为了解决这个问题，我们需要考虑机器人在不同金币花费下的弹跳能力，并计算出在每种情况下能够获得的最大分数。我们的目标是找到最小的金币花费，使得获得的分数至少为 kk。

算法步骤

1. 理解问题：机器人可以从起点向右跳，每次跳的距离为 d 或在花费一定金币后增加的灵活性范围内。目标是找到最小的金币花费，使得总分数至少为 k。

2. 预处理：首先，我们需要根据给定的格子位置和分数，构建一个数组或列表，其中每个元素代表一个格子的位置和分数。

3. 动态规划：使用动态规划来计算在不同金币花费下的最大分数。设 dp[g]表示花费 g 金币时可以获得的最大分数。我们需要初始化 dp[0]为在不花费金币时的最大分数，然后逐步增加金币花费，更新 dp 数组。

4. 更新 dpdp 数组：对于每个 g，我们需要考虑所有可能的弹跳距离，并计算在这些距离下可以获得的最大分数。这涉及到遍历所有格子，并尝试所有可能的弹跳组合。

5. 二分查找：由于我们需要找到最小的 g 使得 dp[g]≥kdp[g]≥k，我们可以使用二分查找来优化搜索过程。

6. 边界条件：确保在计算过程中考虑边界条件，例如当 g≥dg≥d 时，机器人可以跳任何距离。

7. 输出结果：如果找到了满足条件的最小 g，则输出这个值；如果没有这样的 g，则输出 −1。

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;int minGoldNeeded(int n, int d, int k, vector<pair<int, int>>& grid) {// 将格子按照位置排序sort(grid.begin(), grid.end());// 计算最大可能的金币花费int maxGold = 0;for (int i = 0; i < n; ++i) {maxGold = max(maxGold, grid[i].first);}// 使用一个哈希表来存储每个位置的最大分数unordered_map<int, int> dp;dp[0] = 0; // 0金币时的分数是0// 遍历每个格子，更新dp表for (int i = 0; i < n; ++i) {int pos = grid[i].first;int score = grid[i].second;for (int g = maxGold; g >= 0; --g) {if (dp.find(g) != dp.end()) { // 如果这个金币花费是有效的int newScore = dp[g] + score;int newGold = g + pos;if (newGold > maxGold) continue; // 如果新金币花费超过最大值，则跳过dp[newGold] = max(dp[newGold], newScore);}}}// 使用二分查找找到最小的金币花费int left = 0, right = maxGold;while (left < right) {int mid = left + (right - left + 1) / 2;if (dp.find(mid) != dp.end() && dp[mid] >= k) {right = mid - 1;} else {left = mid;}}// 如果找不到满足条件的金币花费，返回-1if (dp.find(left) == dp.end() || dp[left] < k) {return -1;}return left;
}int main() {int n = 7, d = 4, k = 10;vector<pair<int, int>> grid = {{2, 6}, {5, -3}, {10, 3}, {11, -3}, {13, 1}, {17, 6}, {20, 2}};int result = minGoldNeeded(n, d, k, grid);cout << result << endl;return 0;
}