【Nowcoder-TOP101】BM1.小明打联盟

题目：
链接：https://ac.nowcoder.com/acm/problem/14553
来源：牛客网

小明很喜欢打游戏，现在已知一个新英雄即将推出，他同样拥有四个技能，其中三个小技能的释放时间和固定的伤害值为：
1.乌鸦坐飞机 释放时间：x 固定伤害值：a
2.蜘蛛吃耳屎 释放时间：y 固定伤害值：b
3.饿狼前进 释放时间：z 固定伤害值：c

他还有一个大招，其释放的时间是一个区间【L,R】，可以在区间内任意时间点释放出技能，其如果在L+i时刻释放技能，其能够打出的伤害值为:temp+A*i
这里temp值表示技能的基础伤害（同时也就是在时刻L释放技能的伤害值）,A是一个常数。

小明很喜欢研究连招使得在有限的时间内打出最高的伤害，现在他想要在T长度单位时间内打出最高的伤害，问这个最大伤害值。

思路：
问题归类：完全背包。
大招蓄力时间有没有收益加成，要看A与temp/L之间的关系：

• A ＜ temp / L：没有受益加成
• A > temp / L：有受益加成
• A = temp / L：可有可无

而A，temp， L皆为由输入获取到的常数，所以有无收益加成，在得到他们的值后即可确定。只要有收益加成，则尽量蓄力；如果没有收益加成，则选择最短蓄力时间即可（此仅针对大招蓄力加成而言）。

故对于[L,R]范围的物品，其实要么选L（未蓄力的大招），要么选R（蓄满力的大招），要么选其它的i（蓄了一部分力的大招） ，这样最优。L和R被当作基本技能转进背包，其他的i 用来补充最后不足以释放小技能的时间，因此要在最后再用蓄力一部分的大招更新一下最优值。
注：之所以不将所有[L，R]范围的物品化为L,L+1,L+2，…L+R，是因为区间范围可能很大，有可能会超时。

解答：

from collections import deque
import sys
deq = deque()
for line in sys.stdin:
        deq += line.strip().split(' ')
while deq:
    skill= []
    T = int(deq.popleft())
    dp = [0]*(T+1)
    skill.append((int(deq.popleft()),int(deq.popleft())))
    skill.append((int(deq.popleft()),int(deq.popleft())))
    skill.append((int(deq.popleft()),int(deq.popleft())))
    L,R,temp,A = int(deq.popleft()),int(deq.popleft()),int(deq.popleft()),int(deq.popleft())
    skill.append((L, temp))
    skill.append((R, temp+A*(R-L)))
    for i,item in enumerate(skill):
        for t in range(item[0], T+1):
            dp[t] = max(dp[t], dp[t-item[0]] + item[1])
   
    for i in range(L+1, R):
        dp[T] = max(dp[T], dp[T-i]+temp+A*(i-L))
    print(dp[T])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23