i794: pD. 這是替身攻擊
Tags : DP 背包
Accepted rate : 10人/14人 ( 71% ) [非即時]
評分方式:
Tolerant

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

Content

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

 

已知己方生命值 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)並不算是擊敗對方。

 

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

Input

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

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

Output

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

Sample Input #1
10 20 4
8 19
7 16
3 4
2 4
Sample Output #1
1
Sample Input #2
10 20 4
8 19
7 16
3 4
5 4
Sample Output #2
wryyyyyyyyyyyyy
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 2.0s , <1K
公開 測資點#1 (5%): 2.0s , <1K
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1K
公開 測資點#4 (5%): 2.0s , <1K
公開 測資點#5 (5%): 2.0s , <1K
公開 測資點#6 (5%): 2.0s , <1K
公開 測資點#7 (5%): 2.0s , <1K
公開 測資點#8 (5%): 2.0s , <1M
公開 測資點#9 (5%): 2.0s , <1M
公開 測資點#10 (5%): 2.0s , <1M
公開 測資點#11 (5%): 2.0s , <1M
公開 測資點#12 (5%): 2.0s , <1M
公開 測資點#13 (5%): 2.0s , <1M
公開 測資點#14 (5%): 2.0s , <1M
公開 測資點#15 (5%): 2.0s , <1M
公開 測資點#16 (5%): 2.0s , <1M
公開 測資點#17 (5%): 2.0s , <1M
公開 測資點#18 (5%): 2.0s , <1M
公開 測資點#19 (5%): 2.0s , <1M
Hint :

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

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


ID User Problem Subject Hit Post Date
32191 mushroom.cs9...(mushroom) i794
題解
32 2022-09-20 09:56