p2678 [noip2015 提高组] 跳石头

题目描述

有一条数轴，长度为n，上面的每个点都可能放有一块石头。现在有一只青蛙在数轴的点，它想跳到数轴的n-1点。如果青蛙在第i个点，它最多可以向右跳ai个单位，当然它也可以选择不跳。现在问你青蛙能否到达数轴的n-1点。

输入格式

第一行一个整数n。

第二行n个整数，第i个整数表示ai。

输出格式

如果能到达，输出“YES”，否则输出“NO”。

数据范围

1≤n≤105,
≤ai≤104

输入样例1：

5
2 1 1

输出样例1：

NO

输入样例2：

5
2 1 1 1

输出样例2：

YES

算法1

(贪心) $O(n)$

1.从开始，每次跳到能跳到的最远的石头上，如果跳不到则返回NO

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

相关问题

p2669 [noip2015 普及组] 金币

题目描述

有 n 个金矿，第 i 个金矿可开采出金子的数量为 g[i]，需要的工人数为 p[i]。有 m 个工人，每个工人只能开采一个金矿，每个金矿最多只能开采一次。

现在需要你编写一个程序，计算出在不超过 m 个工人的情况下，最多可以获得多少金子。

输入格式
第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示每个金矿可开采出的金子数量 g[i]。

第三行包含 n 个整数，表示每个金矿需要的工人数 p[i]。

输出格式
输出一个整数，表示在不超过 m 个工人的情况下，最多可以获得多少金子。

输入样例
5 10
400 500 200 300 350
5 5 3 4 3

输出样例
900

数据范围
1≤n≤1000,1≤m≤10000,0≤g[i],p[i]≤1000

解题思路：

采用动态规划的方式解决。定义状态f(i,j)表示对前i个金矿，用j个工人最多可获得的金子数。
则转移方程为f(i,j)=max{f(i-1,j),f(i-1,j-p[i])+g[i]}
其中f(i-1,j)表示不选择第i个金矿，f(i-1,j-p[i])+g[i]表示选择第i个金矿。
边界条件为f(i,0)=0,f(0,j)=0。
最终答案为f(n,m)。

时间复杂度分析：
共有n*m个状态，每个状态都需要进行一次状态转移，则总时间复杂度为O(nm)。

参考代码：

P1563 [NOIP2016 提高组] 玩具谜题

P1563 [NOIP2016 提高组 玩具谜题是一个关于玩具人隐藏眼镜的谜题。在这个谜题中，Xiaonan拥有一套可爱的玩具人，每个玩具人都有不同的职业。有一天，这些玩具人把Xiaonan的眼镜藏起来了。Xiaonan发现玩具人围成了一个圆圈，一些面向圆圈内部，一些面向圆圈外部。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [P1563 [NOIP2016 提高组] 玩具谜题(找规律，心要细，数学思维）](https://blog.csdn.net/m0_57071296/article/details/119763478)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]