i794. pD. 這是替身攻擊
標籤 : DP 背包
通過比率 : 57人/73人 ( 78% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-09-15 03:47

內容

敵人即將發動替身攻擊,一旦對方發動成功
將會發生比午餐被忘在蒸飯箱直到隔夜更可怕的事情

 

已知己方生命值 W, 對方生命值 E
為了阻止他,你有 N 種不同招式可以先對他攻擊
其中使用招式i,將消耗你 Di 生命值,並給予對方 Ai 傷害

 

當某方生命值歸零時,即代表該方被打敗
又因為冷卻時間的緣故,每種招式至多只能被使用一次

 

舉例來說,假設 W = 10, E = 20, N = 4
N 個招式分別為:招式0(消耗8, 傷害19), 招式1(消耗7, 傷害16), 招式2(消耗3, 傷害4), 招式3(消耗2, 傷害4)

 

可以發現依序發動:招式1 → 招式3
將可在消耗己方 7 + 2 = 9 點生命值的情況下,給予對方 16 + 4 = 20 點傷害,順利擊敗對方

 

你可以搭配任何招式順序組合,
請計算如果想要擊敗對方(總傷害 ≥ E),己方最多可保留多少生命值?
當然,同歸於盡(剩餘生命值 ≤ 0)並不算是擊敗對方。

 

前方高能,非戰鬥人員請迅速撤離
這是替身攻擊!

輸入說明

第一行有三個正整數 W, E, N,
代表己方生命值、對方生命值、可用的招式種數
1 ≤ W ≤ 104
1 ≤ E ≤ 106
1 ≤ N ≤ 104

接著有 N 行,每行有兩個正整數 D和 Ai
代表該招式需消耗生命值、給予對方傷害
1 ≤ Di, Ai ≤ 104

輸出說明

在擊敗對方(總傷害 ≥ E)的情況下,己方最多可保留多少生命值
若找不到任何活著(剩餘生命值 > 0)但擊敗對方的方法,則請印出"wryyyyyyyyyyyyy"

範例輸入 #1
10 20 4
8 19
7 16
3 4
2 4
範例輸出 #1
1
範例輸入 #2
10 20 4
8 19
7 16
3 4
5 4
範例輸出 #2
wryyyyyyyyyyyyy
測資資訊:
記憶體限制: 512 MB
提示 :

10%:N = 3
30%:N ≤ 100
60%:無特別限制 

標籤:
DP 背包
出處:
111學年度hgsh校內賽 [管理者: mushroom.cs9 ... (mushroom) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」