2019.4.5腾讯笔试第三题

2019.4.5腾讯笔试第三题

题目大概：

一个人需要通过一段路，路上有n个怪兽，战斗力为u，贿赂金币为w。必须要依次经过，遇到一只怪兽，有两种选择，

1.贿赂它，给他w金币，怪兽会变成你的小弟，跟着你，它的战斗力会给你。

2.打败他，当你的小弟的战斗力之和大于它，就可以打败他。

最后求通过这段路的最小金币是多少。

n最大是50。

u最大是1e12。

w最大是2。

思路：

首先这是一个给n个数，选或者不选的问题。这类问题可以爆搜解决，但是数据为50，最坏时间复杂度会到2^50.

那么可以考虑动态规划的01背包。

那背包的容量是什么呢，可以用金币做容量。

因为最大金币数50*2=100.所以很小。从时间和数组的大小考虑都可以接收。

状态为：

dp[i][0][j] 表示经过前i只怪兽，一共花费了j金币贿赂怪兽，最后一只怪兽不贿赂的最大战斗力。

dp[i][1][j] 表示经过前i只怪兽，一共花费了j金币贿赂怪兽，最后一只怪兽贿赂的最大战斗力。

状态转移都比较容易实现，可以看一下代码。

这样算出来，只需要遍历一遍，求经过前n只怪兽，有战斗力状态的最小金币就可以了。

AC代码：

#include using namespace std;#define ll long longconst int mod=1e9+7;const int INF=0x3f3f3f3f;struct node{ ll u; int w;}G[60];ll dp[55][2][120];int main(){ int n; cin>>n; int sum=0; for(int i=0;i=0;j--) { if(dp[i-1][0][j]>=G[i].u)dp[i][0][j]=dp[i-1][0][j]; if(dp[i-1][1][j]>=G[i].u)dp[i][0][j]=max(dp[i-1][1][j],dp[i][0][j]); if(j>=G[i].w){ if(dp[i-1][0][j-G[i].w])dp[i][1][j]=dp[i-1][0][j-G[i].w]+G[i].u; if(dp[i-1][1][j-G[i].w])dp[i][1][j]=max(dp[i-1][1][j-G[i].w]+G[i].u,dp[i][1][j]); } } } for(int i=0;i<=sum;i++) { if(dp[n-1][0][i]){ cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。