腾讯正式批笔试-后台开发 编程题题解

求第一题详细思路

第三题用了dfs也行，第一题想不出来。。我以为是dp，做对2道应该有面试机会吧。。。 #include<bits/stdc++.h> using namespace std; unsigned long long arr1[100]; // 武力 int arr2[100]; // 金币 int n; int ans = 0x7fffff; void dfs(int i, int cur, unsigned long long a) { if(cur >= ans) return; if(i==n) { ans = min(ans, cur); return ; } if(a < arr1[i]) { dfs(i+1, cur+arr2[i], a+arr1[i]); } else { dfs(i+1, cur+arr2[i], a+arr1[i]); dfs(i+1, cur, a); } } int main() { int n; cin>>n; for(int i=0;i<n;i++) cin>>arr1[i]; for(int i=0;i<n;i++) cin>>arr2[i]; dfs(0, 0, 0); cout << ans << endl; }

第三题，测试用例4，8 5 10 14，1 1 2 2的情况输出应该是3，但照这个思路输出不是4么

dp啊 ，f[i][j]表示前i个怪兽花费j元 能获得的最大武力值 ，转移的时候判断武力值够不够继续转移，最后再check一下最小满足所有的j是多少 就是答案啊

怪兽本来也是这么想。。后来自己写了个样例发现如果武力比他高还是2也可能要买就不会了。。

为何这么强

那如果金币不是固定的呢

请问lz第一题是100%吗？我思路一样，不过是最后十秒交的，没来得及看结果

武力8 3 5 10 19 36 金钱1 1 1 2 2 2如果不考虑2元怪兽的话答案是6但是我算的是5就不会敲了可以帮忙看下吗😭

mark一下

当前武力值少于，价格2，看看买堆顶怪兽行不行，行就买，不行就买现在这个 大佬这里说的取堆顶怪兽是不是应该至少取一个，至多取两个呢？堆中每个怪兽的金币值都为1， 如果取出一个怪兽还是打不过当前金币值为2的怪兽的话，就从堆中再取出一个，之后比较从 堆中取出的这两个怪兽的武力值与当前打不过的怪兽的武力值哪个大，然后买武力值较大的 一种方案，花费的金币数可能为1或2.

第三题暴力搜索 https://paste.ubuntu.com/p/vBMDBFmf2w/