[NOIP2005]过河题目题解

Kur1su

发表于 2020-05-09 19:31:43

最近作业越来越多了啊, 每天写个每日一题都是奢求 Solution 观察题目数据范围石子的数目很少 , 青蛙跳的步幅但是总长度却是级别的假如很小的话, 我们很容易考虑表示第这个位置踩的最小石头数有转移方程考虑上图的情况, 在高达的时候, 每个石头之间的距离将会很大展开全文

与人无语

发表于 2020-05-16 01:26:11

这一看是一个简简单单的dp 转移方程一下子就推出来了但是一写就发现范围怎么这么大（憨批如我还真开了一次1e9的数组)这题击中了我的盲区 but 我的巨佬队友说这题太基础了（在洛谷有三万多提交这题主要是离散化（名词真熟悉不会在翻阅了十几篇题解过后我终于明白了离散化就是在一个大范围内目展开全文

19_hanhan

发表于 2020-05-11 01:10:23

题目题目描述：在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标展开全文

平凡的小白

发表于 2020-05-09 10:31:58

Question：青蛙从桥头跳过独木桥，跳过就行，桥长为，青蛙跳过的路程只要大于等于就行。桥上有一些石头，题目会给石头的数量m和m个石头的位置，还有青蛙跳跃的最小距离s、最大距离t。 Analysis：离散化+dp。这个离散化和我学过的不一样，我之前学的离散化是把一个大的集合向一个展开全文

瑜画

发表于 2020-06-12 17:06:11

状态转移方程非常简单，dp[i]=min(dp[i],dp[j]+b[i])然而L高达10的9次方，但是石头的个数只有最多100个，有效的石头数目很少，但是他们分布的空间很广，符合离散化的特点，所以这道题是离散化dp 首先，这道题没有说石头的位置是按顺序输入的，所以要先对石头进行升序排序。接下来就进展开全文

shyyhs

发表于 2021-01-20 11:20:01

把数组开到极限,以及将可以在中间转化的值全部消除然后进行dp即可. #include <bits/stdc++.h> using namespace std; const int mod=2*3*4*5*6*7*8*9*2; const int N=1e2+5; const int M= 展开全文

HBlade

发表于 2020-05-12 17:56:47

首先这个题DP应该是挺容易看出来的，就是一个线性的东西，后面的可以从前面的转移。然后既然想到了DP，可以决定一下DP的状态，很显然可以定dp[i]为到位置i的时候最少踩多少个石子。再然后就是转移方程了，对于s<=j<=t,并且i>=j,dp[i]=min(dp[i],dp[i-j 展开全文

精神病科黄主任

发表于 2020-05-09 01:26:50

题目描述在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终展开全文

nagisa_菜鸡

发表于 2020-05-18 12:14:20

思路首先，这道题还是比较容易能想到可能可以用dp解决的，因为最终的结果可以由前面的问题的解推出，具有最优子结构的特点。然而，问题是桥长度长达1e9，开不了这么大的dp数组。对于数据范围较大导致暴空间，我们的一个处理方法就是离散化。但是这里需要怎么离散化呢？看了大佬的题解(膜拜一下orz)，由于s和展开全文

Leida_徐晓雅

发表于 2020-05-15 00:08:28

题目描述在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终展开全文

相关比赛

等你来战