最近追加された問題保存した問題Workbooks

カテゴリ DLC コンテストグループチーム掲示板

ランキング

正解数ランキングストリークランキングDOJ Powerランキング

問題募集ログイン新規登録

DOJ

OI形式のサブタスク採点、Eloレーティング、Discord認証を備えたオンラインジャッジです。

問題

問題一覧カテゴリ

コミュニティ

コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド

アカウント

ログイン新規登録ジャッジ状態

ポリシー

利用規約 DLCの利用規則プライバシー API 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス

© 2026 DOJ

All rights reserved

解説

루미의 스트레스 해소하기

問題に戻る

解説

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)

입니다.