最近在玩海岛奇兵, 里面有
武器A, 第n次使用消耗(10 + 6 * (n - 1))点能量并造成18315伤害;
武器B, 第n次使用消耗 (3 + 2 * (n - 1))点能量并造成8124伤害,
就想着能不能写一个程序计算一下, 当有x点能量时, 可造成的最大伤害是多少? 分别使用AB武器各多少次?
讨论: https://leetcode.cn/circle/discuss/vZu06x/
总觉得除了暴力还有更好的算法, 但是不知道怎么做
def multiple_rocket_launcher(n: int): """ 计算多管火箭发射器造成的伤害值 :param n: 发射的火箭数量 :return: 返回伤害值 """ return 10 + 6 * (n - 1) def artillery(n: int): """ 计算火炮造成的伤害值 :param n: 发射的火炮数量 :return: 返回伤害值 """ return 3 + 2 * (n - 1) def multiple_rocket_launcher_total_energy(n: int): """ 计算发射 n 枚多管火箭发射器需要的总能量值 :param n: 发射的火箭数量 :return: 返回总能量值 """ return n * (10 + multiple_rocket_launcher(n)) // 2 def artillery_total_energy(n: int): """ 计算发射 n 枚火炮需要的总能量值 :param n: 发射的火炮数量 :return: 返回总能量值 """ return n * (3 + artillery(n)) // 2 def max_multiple_rocket_launcher_count(energy_value: int): """ 计算 energy_value 点能量值最多可以发射多少枚多管火箭发射器 :param energy_value: 可消耗的能量值 :return: 返回最多可以发射的多管火箭发射器数量 """ multiple_rocket_launcher_count = 0 while multiple_rocket_launcher_total_energy(multiple_rocket_launcher_count + 1) <= energy_value: multiple_rocket_launcher_count += 1 return multiple_rocket_launcher_count def max_artillery_count(energy_value: int): """ 计算 energy_value 点能量值最多可以发射多少枚火炮 :param energy_value: 可消耗的能量值 :return: 返回最多可以发射的火炮数量 """ artillery_count = 0 while artillery_total_energy(artillery_count + 1) <= energy_value: artillery_count += 1 return artillery_count def maximum_injury_value(energy_value: int): """ 计算 energy_value 点能量值可造成的最大伤害值 :param energy_value: 可消耗的能量值 :return: 返回最大伤害值 """ if energy_value <= 0: print("能量值必须大于0") return multiple_rocket_launcher_injury_value = 18315 artillery_injury_value = 8124 i = max_multiple_rocket_launcher_count(energy_value) use_list = [] while i >= 0: surplus = energy_value - multiple_rocket_launcher_total_energy(i) j = max_artillery_count(surplus) total_damage = i * multiple_rocket_launcher_injury_value + j * artillery_injury_value # print(f"多管火箭发射器数量：{i}, 火炮数量：{j}, 伤害值", "{:,}".format(total_damage)) use_list.append((i, j, total_damage)) i -= 1 # 根据伤害值排序 use_list.sort(key=lambda x: x[2], reverse=True) return use_list[0]
或者递归, 效率很低但是代码很优雅简洁
int dfs(int i, int j, int energy) { int energy_a = 10+6*(i-1); int energy_b = 3+2*(j-1); int damage_a = 0; int damage_b = 0; //选择火箭递归 if (energy_a <= energy) damage_a = dfs(i+1, j, energy - energy_a) + 18315; //选择火炮递归 if (energy_b <= energy) damage_b = dfs(i, j+1, energy - energy_b) + 8124; return max(damage_a, damage_b); } int main() { int energy = 100; int res = dfs(1, 1, energy); return 0; } //作者：changelog //链接：https://leetcode.cn/circle/discuss/vZu06x/view/vXS6oX/ //来源：力扣（LeetCode） //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
然后对常有能量值画了个图
