首页 > 宝藏猎人

ddhw111

发表于 2024-06-13 21:28:15

链接：https://ac.nowcoder.com/acm/problem/236173 来源：牛客网有一片群岛，总共有30001个岛屿，编号从0到30000，其中有 n 个宝藏在这些岛屿中。Kitayuta是一位宝藏猎人，他初始在0号岛屿上。为了获得宝藏，他按照如下规则经过这些岛屿：展开全文

Z_L_G

发表于 2025-05-10 11:44:43

题意共有0~30000编号的岛，有n个宝藏，你每次只能往编号大的方向走，走的步长只能是上一次走的步长+p（p=-1,0,1），第一步走了d，求最多能拿到多少宝藏思路本题应该使用dfs+剪枝是更好写的 dp 对于0~30000这个范围，从1开始走，最大的偏移量不超过300 即相较于第一步展开全文

在刷题的单身狗很开心

发表于 2023-10-18 16:36:17

本题直接使用dfs，然后配合剪枝去接最好。直接dfs的去进行每一步当递归到最大的拥有宝藏的岛屿的下一个就可以宣布结束返回了。如何剪枝：本题中dfs是从前向后的传参形的记录当前的宝藏数量，那么如果某个岛屿第二遍被递归到的时候如果当前的宝藏数还没有之前的大。那么再递归下去就没有意义了。这展开全文

Hui1631

发表于 2024-08-03 15:05:30

由于到达下一点只可能产生{1,0,-1}的变化; 假设一直递降, 即操作为d, d-1, d-2, d-3, ..为等差数列. 设极限情况末尾速度为0, 即路程和为(n-1)*n/2 <= 30000 -> 求得n<300; 取n=300, 暴力枚举下复杂度为30000300(长度展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛