求各位大佬分享一手腾讯笔试第三题贿赂怪兽的解题思路😀

dfs爆搜过了，还以为会会被卡时间

dp[i][j]表示到第i个花了j块钱最多有多少武力值

直接看当前打不打的过，打的过pass，打不过就贿赂，这么low的贪心算法直接过了80%你敢信...🤣🤣

嘤嘤嘤

打的过就打，打不过充钱过了。（虽然不合理，但是确实过了）

public static int f(long wu, int mon, int i){ if(i == n-1) { if(wu<w[i]) { return mon + m[i]; }else { return mon; } } if(wu<w[i]) { return f(wu+w[i], mon+m[i], i+1); }else { return Math.min(f(wu+w[i], mon+m[i], i+1), f(wu, mon, i+1)); } }不知道行不行，考完才写出来的。

怪兽要考虑出现顺序吗

暴搜反而不会写 dp[i]：前i个怪兽所要最小金币

我感觉10^12的数据...正解是超大背包，用折半枚举（至于dfs（2^N）为啥AC真的很疑惑，例子太水了？贪心肯定是错的）

这题为什么不是打的过就打，打不过就贿赂……题目说了依次遇到这些怪兽啊。。

贪心就是最合理的解法，这可以化作一个0-1线性规划，没有多项式时间解法。贪心起码是2近似。