最近添加的题目收藏的题目Workbooks

分类 DLC 比赛小组团队讨论区

解题数量排行榜连续解题排名DOJ Power 排行榜

征题登录注册

DOJ

支持 OI 子任务计分、Elo 等级分和 Discord 认证的社区在线评测系统。

题目

题目列表分类

社区

比赛排名讨论区公告举办外部比赛指南

账号

登录注册评测状态

政策

服务条款 DLC 使用规则隐私政策 API 文档语言运行环境比赛排名奖励评级与表现

© 2026 DOJ

保留所有权利

题解

루미의 스트레스 해소하기

题解

DP 문제입니다. $dp[t][s]$ 를 $t$ 분이 지났고 체력을 $s$ 이하로 썼을 때 스트레스의 최솟값으로 둡니다.
처음에는 취미를 하나도 하지 않은 경우로 채웁니다: $dp[t][s] = A + tF$ .
$t$ $t$ , $s$ $s$ 를 $1$ $1$ 부터 늘려 가며, 각 취미(해소량 $L$ $L$ , 소모 시간 $H$ $H$ , 체력 소모량 $M$ $M$ )에 대해 갱신합니다.
- $t \geq H$ 이고 이면 취미를 시작할 때의 체력은 이고, 이 값으로 를 구합니다.

dp[t][s] = \max(0,\ \min(dp[t][s],\ dp[t][s-1],\ dp[t-1][s] + F,\ dp[t-H][s-M] - L_{eff}))

그 취미를 할 수 없으면 마지막 항만 빼고 갱신합니다.

dp[t][s] = \max(0,\ \min(dp[t][s],\ dp[t][s-1],\ dp[t-1][s] + F))

같은 취미를 여러 번 할 수 있으므로 $dp[t-H][s-M]$ 은 같은 표의 값을 그대로 씁니다.
답은 $dp[B][C]$ 입니다.
주의할 점
- 취미를 즐기지 않는 동안에는 $1$ 분마다 스트레스가 씩 오릅니다.

t \ge H

t \geq H

s \ge M

C - (s - M)

L_{eff}

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

F

E > 100

이면

L_{eff}

가 음수가 됩니다. 음수를 양수로 나눈 결과는 언어마다 다르니 주의합시다. 지문의

L_{eff}

는 내림입니다.

스트레스의 최솟값은

0

입니다.

시간복잡도는

\mathcal{O}(NBC)

, 공간복잡도는

\mathcal{O}(BC)

입니다.