Hackerrank 竞赛：动态规划

Question

我在 hackerrank（link 下面）上遇到了一个竞赛问题

https://www.hackerrank.com/contests/w13/challenges/a-super-hero

据我所知，这是一个动态规划问题。我尝试了各种方法，但未能清除它。它有一个冗长的问题陈述，但我会尽量简短地解释它。

您必须清除 n 个不同的关卡，每个关卡包含 m 个敌人。每个级别都可以通过击败该级别的 任何一个敌人 来清除。每个敌人都有 一些子弹和一些能量 。你需要和他的力量一样多的子弹来打败他。击败敌人后，你可以拿走他的子弹，只能在下一级使用。所以，你必须告诉，最少没有。开始时需要多少子弹 才能完成游戏。

详情请见link。

不需要完整的解决方案。只是一些指点，提示就足够了。

Answer 1

其实这个问题不是DP。这是一个二进制搜索问题。对答案进行二进制搜索。对于每个子弹数 N，在每个级别上 greedy。也就是说，在你可以杀死的敌人中（即威力不超过你当前的子弹），在关卡结束后杀死一个会给你最多子弹的敌人。请注意，在这里您需要减去杀死给定敌人所需的子弹数量。如果初始值 N 足以完成所有级别，则将其设置为搜索范围的新结束点。否则将 N 设置为新的开始（常规二进制搜索方法）。