做个什么类型网站,微信营销号是啥意思,网站建设那里好,定制开发网站题目描述
跳房子#xff0c;也叫跳飞机#xff0c;是一种世界性的儿童游戏#xff0c;也是中国民间传统的体育游戏之一。
跳房子的游戏规则如下#xff1a;
在地面上确定一个起点#xff0c;然后在起点右侧画 n 个格子#xff0c;这些格子都在同一条直线上。每个格子内…
题目描述
跳房子也叫跳飞机是一种世界性的儿童游戏也是中国民间传统的体育游戏之一。
跳房子的游戏规则如下
在地面上确定一个起点然后在起点右侧画 n 个格子这些格子都在同一条直线上。每个格子内有一个数字整数表示到达这个 格子能得到的分数。玩家第一次从起点开始向右跳跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳依此类推。规则规定
玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏获得的分数为曾经到达过的格子中的数字之和。
现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷它每次向右弹跳的距离只能为固定的 d。小 R 希望改进他的机器人如果他花 g 个金币改进他的机器人那么他的机器人灵活性就能增加 g但是需要注意的是每 次弹跳的距离至少为 11。具体而言当 gdgd 时他的机器人每次可以选择向右弹跳的距离为 d−g,d−g1,d−g2,…,dg−1,dgd−g,d−g1,d−g2,…,dg−1,dg否则当 g≥dg≥d 时他的机器人每次可以选择向右弹跳的距离为 1,2,3,…,dg−1,dg1,2,3,…,dg−1,dg。
现在小 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≤5001≤d≤2×1031≤d≤2×1031≤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]≤dg
注w[i]为i个格子的得分 时间复杂度 O(n×d×logxn) 需要对DP进行剪枝。 #includeiostream
#includequeue
#includecstring
#includecmath
using namespace std;
typedef long long ll;
int n,d,k;
int a[500010][2];
ll f[500010],sum0;
bool check(int g) {coutgg endl;int lmax(1,d-g),rdg;cout%%%l rendl;memset(f,-127,sizeof f);f[0]0;for(int i1; in; i) {//每个格子int td;for(int j0; ji; j) {//当前格子的前面格子,从小到大去寻找tda[i][0]-a[j][0];cout格子***j 格子举例tdendl;if(tdltdr) {// f[i]积分当前i格子的分数f[i]max(f[i],f[j]a[i][1]);}if(f[i]k) return true;if(tdl) break;}couti f[i]endl;}return false;
}int main() {scanf(%d %d %d,n,d,k);for(int i1; in; 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(sumk) {//所有的正分加起来都不够希望获得的分数printf(-1);return 0;}//二分int l0,rmax(0,a[n][0]-d);cout a[ n-1 ][0] a[n][0] endl;cout d d endl;while(lr) {cout*l rendl;int mid(lr)/2;if(check(mid)) rmid;else lmid1;}printf(%lld,l);return 0;
} 解答2基本思想
要解决这个问题我们需要动态规划Dynamic ProgrammingDP的思想。我们要确定最少需要花费多少金币来改造机器人使其能够获得至少 k 分。以下是详细的步骤和思路 输入处理 读取 n, d, k。读取每个格子的位置和分数。 确定DP状态 dp[i][j] 表示花费 j 个金币时到达第 i 个格子能获得的最大分数。 状态转移 对于每个格子 i 和每个花费 j我们需要尝试所有可能的跳跃距离并更新 dp[i][j]。跳跃距离的范围根据 g 和 d 的关系分为两种情况 当 g d 时跳跃距离范围是 [d-g, dg]。当 g d 时跳跃距离范围是 [1, dg]。 初始化 起点位置特殊处理dp[j] 初始化为 0起点没有分数但是可以作为跳跃的出发点。 结果计算 遍历所有格子和所有花费计算能得到的最大分数。最终找到最小的花费 j 使得在某个格子上的分数大于等于 k。 边界情况处理 如果无法获得至少 k 分返回 -1。
以下是实现该算法的C代码
#include iostream
#include vector
#include algorithm
#include climitsusing namespace std;struct Grid {int position;int score;
};int main() {int n, d, k;cin n d k;vectorGrid grids(n);for (int i 0; i n; i) {cin grids[i].position grids[i].score;}// 由于位置是按递增顺序输入的我们可以直接使用下标来访问格子vectorvectorint dp(n 1, vectorint(n 1, -1)); // n1 个格子, 最多花费 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。
算法步骤 理解问题机器人可以从起点向右跳每次跳的距离为 d 或在花费一定金币后增加的灵活性范围内。目标是找到最小的金币花费使得总分数至少为 k。 预处理首先我们需要根据给定的格子位置和分数构建一个数组或列表其中每个元素代表一个格子的位置和分数。 动态规划使用动态规划来计算在不同金币花费下的最大分数。设 dp[g]表示花费 g 金币时可以获得的最大分数。我们需要初始化 dp[0]为在不花费金币时的最大分数然后逐步增加金币花费更新 dp 数组。 更新 dpdp 数组对于每个 g我们需要考虑所有可能的弹跳距离并计算在这些距离下可以获得的最大分数。这涉及到遍历所有格子并尝试所有可能的弹跳组合。 二分查找由于我们需要找到最小的 g 使得 dp[g]≥kdp[g]≥k我们可以使用二分查找来优化搜索过程。 边界条件确保在计算过程中考虑边界条件例如当 g≥dg≥d 时机器人可以跳任何距离。 输出结果如果找到了满足条件的最小 g则输出这个值如果没有这样的 g则输出 −1。
#include iostream
#include vector
#include algorithm
#include unordered_map
using namespace std;int minGoldNeeded(int n, int d, int k, vectorpairint, int grid) {// 将格子按照位置排序sort(grid.begin(), grid.end());// 计算最大可能的金币花费int maxGold 0;for (int i 0; i n; i) {maxGold max(maxGold, grid[i].first);}// 使用一个哈希表来存储每个位置的最大分数unordered_mapint, 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;vectorpairint, 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;
}
