B. Frog Traveler(cf)bfs
原题链接:Problem - 1601B - Codeforces
题目大意:一个青蛙它从井底跳出去。从x点可以网上蹦[0, ax]的距离到y点,到了y点之后又会掉下来by步。问你它最少走多少步出去。问最少步数,想到用bfs。改了一下午代码,真的好细节呜呜。
思路:它其实每次能向上跳到的范围一直往上,用mmin记录,往下跳的点和网上跳的点维护的东西不一样啊啊我又写不出来了但是我有时候能想清楚。这个博主画的图还有写的文很详细:Codeforces-1601 B: Frog Traveler_盖乌咪·A·埃迪尔的博客-CSDN博客
之前看别的博主写的dp先滑再跳,我不是很懂。还是按照顺序来吧。挺难的毕竟1900的题呜呜呜~继续加油!
每个点最多进入队列一次,然后我们又给他加了限制,所以复杂度是O(n)的。
AC代码:
#include
using namespace std;
#define INF 0x3f3f3f3f
typedef pair
const d
共有 0 条评论