Editorial
- DP 문제입니다. dp[t][s]를 t분이 지났고 체력을 s 이하로 썼을 때 스트레스의 최솟값으로 둡니다.
- 처음에는 취미를 하나도 하지 않은 경우로 채웁니다: dp[t][s]=A+tF.
- t, s를 1부터 늘려 가며, 각 취미(해소량 L, 소모 시간 H, 체력 소모량 M)에 대해 갱신합니다.
- 이고 이면 취미를 시작할 때의 체력은 이고, 이 값으로 를 구합니다.
dp[t][s]=max(
- 그 취미를 할 수 없으면 마지막 항만 빼고 갱신합니다.
dp[t][s]=max(0, min(dp[t][s
- 같은 취미를 여러 번 할 수 있으므로 dp[t−H][s−M]은 같은 표의 값을 그대로 씁니다.
- 답은 dp[B][C]입니다.
- 주의할 점
- 취미를 즐기지 않는 동안에는 분마다 스트레스가 씩 오릅니다.
t≥H
C−(s−M) 0
,
min
(
d
p
[
t
]
[
s
]
,
d
p
[
t
]
[
s
−
1], dp[t−
1][s]+
F, dp[t−
H][s−
M]−
Leff))
]
,
d
p
[
t
]
[
s
−
1], dp[t−
1][s]+
F))
1
E>100이면 Leff가 음수가 됩니다. 음수를 양수로 나눈 결과는 언어마다 다르니 주의합시다. 지문의 Leff는 내림입니다. 시간복잡도는 O(NBC), 공간복잡도는 O(BC)입니다. 