最近作业越来越多了啊, 每天写个每日一题都是奢求 Solution 观察题目数据范围 石子的数目很少 , 青蛙跳的步幅 但是总长度 却是 级别的假如 很小的话, 我们很容易考虑 表示第 这个位置踩的最小石头数有转移方程 考虑上图的情况, 在 高达 的时候, 每个石头之间的距离 将会很大
展开全文
这一看是一个简简单单的dp 转移方程一下子就推出来了但是一写就发现 范围怎么这么大（憨批如我还真开了一次1e9的数组)这题击中了我的盲区 but 我的巨佬队友说这题太基础了（在洛谷有三万多提交这题主要是离散化（名词真熟悉 不会在翻阅了十几篇题解过后 我终于明白了离散化就是在一个大范围内 目
展开全文
题目 题目描述： 在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。 在桥上有一些石子，青蛙很讨厌踩在这些石子上。 由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。 坐标
展开全文
Question： 青蛙从桥头跳过独木桥，跳过就行，桥长为 ，青蛙跳过的路程 只要大于等于 就行。桥上有一些石头，题目会给石头的数量m和m个石头的位置，还有青蛙跳跃的最小距离s、最大距离t。 Analysis： 离散化+dp。这个离散化和我学过的不一样，我之前学的离散化是把一个大的集合向一个
展开全文
状态转移方程非常简单，dp[i]=min(dp[i],dp[j]+b[i])然而L高达10的9次方，但是石头的个数只有最多100个，有效的石头数目很少，但是他们分布的空间很广，符合离散化的特点，所以这道题是离散化dp 首先，这道题没有说石头的位置是按顺序输入的，所以要先对石头进行升序排序。接下来就进
展开全文
把数组开到极限,以及将可以在中间转化的值全部消除然后进行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=
展开全文
首先这个题DP应该是挺容易看出来的，就是一个线性的东西，后面的可以从前面的转移。 然后既然想到了DP，可以决定一下DP的状态，很显然可以定dp[i]为到位置i的时候最少踩多少个石子。再然后就是转移方程了，对于s<=j<=t,并且i>=j,dp[i]=min(dp[i],dp[i-j
展开全文
题目描述在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终
展开全文
思路 首先，这道题还是比较容易能想到可能可以用dp解决的，因为最终的结果可以由前面的问题的解推出，具有最优子结构的特点。然而，问题是桥长度长达1e9，开不了这么大的dp数组。对于数据范围较大导致暴空间，我们的一个处理方法就是离散化。但是这里需要怎么离散化呢？看了大佬的题解(膜拜一下orz)，由于s和
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
