中兴算法编程打怪兽解析：
总共有n个技能，怪兽有m血，每个技能有A[i]的基础伤害，当怪兽剩余血量小于等于x[i]时可以暴击，造成2*A[i]的伤害，每个技能最多释放一次，求击杀怪兽的最少技能释放次数，若无法击杀则返回-1。
要是这个题没有暴击机制的话就是一个背包问题，对于每一个技能都有释放和不释放两种状态，很好解决。
有了暴击机制对于每一个技能就有释放（暴击和不暴击）和不释放两种状态。因此使用动态规划来解决。
做了一些空间优化和修改：
定义状态：dp[i][j][k]表示仅仅使用前i个技能，怪兽血量是j，该技能释放前已经暴击过的伤害是k，即若k=10，相当于怪兽初始血线为j+k，只有该技能的暴击血线大于j+k技能才能造成暴击。
#状态转移方程：对于第i个技能只有三种释放状态，不释放、暴击、非暴击
预处理：将技能按照暴击血线降序排列，这样才能满足当前技能如果造成暴击伤害bv，则前面技能只能从bv的血线开始打怪兽。否则若当前的技能造成暴击伤害，之前的技能也可能从更高的血线造成暴击。
##不释放情况下：dp[i][j][k]=dp[i-1][j][k]
##暴击：只有x[i]>k的情况下才能造成暴击。dp[i][j][k]=1+dp[i][j-bv][k+bv],bv表示当前技能暴击造成的最大伤害，bv=min(j,2*A[i],x[i]-k)，即当前血量、最大暴击伤害、最大暴击血线减去当前血线的最小值。
##不暴击：dp[i][j][k]=1+dp[i][j][k-A[i]]
空间优化：由于当前状态 i 只与 i - 1 的状态有关，因此仅保留奇数和偶数两个状态迭代更新。
##时间复杂度 n*m*(max(x))
##空间复杂度 2*m*(max(x))
代码如下：
n,m=3,100 A=[10,45,5] x=[20,90,40] # A=[10,45,5] # x=[20,84,40] # A=[10,45,5,30,20,20] # x=[20,85,40,150,50,15] XA=sorted(zip(x,A),key=lambda d:d[0],reverse=True) #[(150, 30), (90, 45), (50, 20), (40, 5), (20, 10), (15, 20)] x,A=[xa[0] for xa in XA],[xa[1] for xa in XA] max_x=XA[0][0] dp=[[[n+1]*(max_x+1) for _ in range(m+1)] for _ in range(2)] for j in range(m+1): for k in range(max_x+1): if j==0: dp[0][j][k]=0 elif j<=A[0]: dp[0][j][k]=1 elif j<=min(x[0]-k,2*A[0]): dp[0][j][k]=1 for i in range(1,n): for j in range(m+1): for k in range(max_x+1): if j==0: dp[i%2][j][k]=0 elif x[i]<k:##无法暴击,释放A[i]和不释放A[i] dp[i%2][j][k]=min(dp[(i-1)%2][j-A[i]][k]+1,dp[(i-1)%2][j][k]) else:##可暴击,释放A[i]、暴击释放A[i]和不释放A[i] bv=min(j,2*A[i],x[i]-k)##暴击值 dp[i%2][j][k]=min(dp[(i-1)%2][j-A[i]][k]+1,dp[(i-1)%2][j-bv][k+bv]+1,dp[(i-1)%2][j][k]) print(dp[(n-1)%2][-1][0] if dp[(n-1)%2][-1][0]<n+1 else -1)
全部评论
(3) 回帖