跳房子（弱化版）

题目描述

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

跳房子的游戏规则如下：

在地面上确定一个起点，然后在起点右侧画 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,kn,d,k，分别表示格子的数目，改进前机器人弹跳的固定距离，以及希望至少获得的分数。相邻两个数 之间用一个空格隔开。

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

输出格式

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

输入格式

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

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

输出格式

共一行，一个整数，表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 kk 分，输出 −1−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。

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

分析与解答： 

解答1：

要解决这个问题，我们需要动态规划（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)，在合理的数据范围内是可以接受的。

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

解答2： 

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