Problem:


Score : 500 points

Problem Statement

Ibis is fighting with a monster.

The health of the monster is H.

Ibis can cast N kinds of spells. Casting the i-th spell decreases the monster's health by A_i, at the cost of B_i Magic Points.

The same spell can be cast multiple times. There is no way other than spells to decrease the monster's health.

Ibis wins when the health of the monster becomes 0 or below.

Find the minimum total Magic Points that have to be consumed before winning.

Constraints

1 \leq H \leq 10^4

1 \leq N \leq 10^3

1 \leq A_i \leq 10^4

1 \leq B_i \leq 10^4

All values in input are integers.

Input

Input is given from Standard Input in the following format:

H N
A_1 B_1
:
A_N B_N

Output

Print the minimum total Magic Points that have to be consumed before winning.

Sample Input 1

9 3
8 3
4 2
2 1

Sample Output 1

4

First, let us cast the first spell to decrease the monster's health by 8, at the cost of 3 Magic Points. The monster's health is now 1.

Then, cast the third spell to decrease the monster's health by 2, at the cost of 1 Magic Point. The monster's health is now -1.

In this way, we can win at the total cost of 4 Magic Points.

Sample Input 2

100 6
1 1
2 3
3 9
4 27
5 81
6 243

Sample Output 2

100

It is optimal to cast the first spell 100 times.

Sample Input 3

9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461

Sample Output 3

139815



Sample input:
9 3
8 3
4 2
2 1


Sample output:
4

Submission status: Accepted

Solution code:
#個数が無制限のナップザックの問題(ただし、上限に注意)です(どの魔法を順番に選べば良いなどの制約がないのでナップザックDPを選択しました。)。
#dpの配列にはi番目の要素にモンスターの体力をi減らすために必要な最小の魔力を保存します。
#この配列は個数制限がないことに注意してinfではない要素のみを順に更新していけば良いです。
#また、最終的にモンスターの体力を最小の魔力で0以下にすれば良いので、モンスターの体力をh以上減らせる最小の魔力を求めれば良いです。

h,n=map(int,input().split())
a,b=[],[]
for i in range(n):
    a_sub,b_sub=map(int,input().split())
    a.append(a_sub)
    b.append(b_sub)
inf=10000000000000
ma=max(a)#ダメージの最大値

dp=[inf]*(h+1+ma)#与えるダメージの最大値を考慮したDP
dp[0]=0#初期値

for i in range(h+1+ma):# 与えるダメージ合計：0ーH+1+maまで
    if dp[i] == inf:#更新してきて、ダメージiになる組み合わせが存在しない場合は飛ばす
        continue
    for j in range(n):    #N個の魔法を試す
        ni = i + a[j] #今の状態から新しく与えた場合のダメージ合計
        if ni<h+ma:#オーバーキルの範囲を超えるなら、無視
            dp[ni] = min(dp[ni], dp[i] + b[j])        #ダメージniを与えるのにより小さい魔力で実現できる場合は更新
print(min(dp[h:]))

Submission status: Accepted

Solution code:
h, n = map(int, input().split())
ab = []
for _ in range(n):
    ab.append(list(map(int, input().split())))
inf = 1001001001
lis = [inf] * (2*10**4+5)
lis[0] = 0
for i in range(len(lis)):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        if i+a < len(lis):
            lis[i+a] = min(lis[i]+b, lis[i+a])
print(min(lis[h:]))

Submission status: Accepted

Solution code:
#n=int(input())
h,n=map(int,input().split())
#a=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(n)]
#l=[list(input().split()) for i in range(n)]


        
ldp=[[0 for j in range(h)]for i in range(n)]
for i in range(n):
    for j in range(h):
        if i==0:
            ldp[i][j]=-(-(j+1)//l[i][0])*l[i][1]
        else:
            if j>=l[i][0]:
                ldp[i][j]=min(ldp[i-1][j],ldp[i][j-l[i][0]]+l[i][1])
            else:
                ldp[i][j]=min(ldp[i-1][j],l[i][1])
print(ldp[-1][-1])

Submission status: Accepted

Solution code:
#n=int(input())
h,n=map(int,input().split())
#a=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(n)]
#l=[list(input().split()) for i in range(n)]

amax=0
for i in range(n):
    if amax<l[i][0]:
        amax=l[i][0]
        
ldp=[[0 for j in range(h+amax)]for i in range(n)]
for i in range(n):
    for j in range(h+amax):
        if i==0:
            ldp[i][j]=-(-(j+1)//l[i][0])*l[i][1]
        else:
            if j>=l[i][0]:
                ldp[i][j]=min(ldp[i-1][j],ldp[i][j-l[i][0]]+l[i][1])
            else:
                ldp[i][j]=min(ldp[i-1][j],l[i][1])
print(min(ldp[-1][h-1:]))

Submission status: Accepted

Solution code:
from collections import defaultdict
h,n=map(int,input().split())
INF=float('inf')
ab=defaultdict(lambda: -INF)
for _ in range(n):
  a,b=map(int,input().split())
  ab[b]=max(ab[b],a)
dp=[INF]*(h+max(ab.values())+1)
dp[0]=0
for i in range(1,ab[min(ab.keys())]+1):
  dp[i]=min(ab.keys())
for i in range(ab[min(ab.keys())]+1,h+max(ab.values())+1):
  for m,d in ab.items():
    if i>=d:
      dp[i]=min(dp[i],dp[i-d]+m)
print(min(dp[h:]))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

readline = sys.stdin.buffer.readline


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


sys.setrecursionlimit(10**5)


def main():
    h, n = geta(int)
    a, b = [0] * (n + 1), [0] * (n + 1)
    for i in range(n):
        a[i + 1], b[i + 1] = geta(int)

    INF = 10**9
    dp = [[INF] * (h + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(0, h + 1):
            if j <= a[i]:
                dp[i][j] = min(b[i], dp[i - 1][j])
            else:
                dp[i][j] = min(dp[i][j - a[i]] + b[i], dp[i - 1][j])

    print(dp[n][h])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
[h,n] = [int(i) for i in input().split()]
ab = []
for i in range(n):
    ab.append([int(j) for j in input().split()])
dp =[0] * 10001 + [10 ** 10] * 10000
for i in range(10001,20001):
    for ls in ab:
        dp[i] = min(dp[i],dp[i-ls[0]]+ls[1])
print(dp[10000+h])

Submission status: Accepted

Solution code:
def main():
    H,N = map(int, input().split())
    A,B = [0]*N,[0]*N
    for i in range(N): A[i],B[i]=map(int, input().split())
    # dp[h] := モンスターの体力をh削るための最小合計魔力
    INF = float('inf')
    dp = [INF]*(H+1)
    dp[0] = 0
    for h in range(1,H+1):
        # h削る最小コストを探す
        for a,b in zip(A,B):
            if h-a>=0:
                dp[h]=min(dp[h],dp[h-a]+b)
            else:
                dp[h]=min(dp[h],b)
    print(dp[H])

main()

Submission status: Accepted

Solution code:
H,N = map(int,input().split())
INF = float('inf')
# dp[i] = 攻撃がh以上となるときに考えられる最小の体力消耗
dp = [INF] * (H+1)

for _ in range(N):
  a,b = map(int,input().split())

  for h in range(1, H+1):
    if h <= a:
      dp[h] = min(dp[h],b)
    else:
      dp[h] = min(dp[h],dp[h-a]+b)

print(dp[-1])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

def main():
	H, N = MAP()
	A, B = [0]*N, [0]*N
	for i in range(N):
		A[i], B[i] = MAP()

	dp = [INF]*(H+1)
	dp[0] = 0


	for i in range(N):
		for j in range(H+1):
			if j < A[i]:
				dp[j] = min(dp[j], B[i])
			if j>= A[i]:
				dp[j] = min(dp[j], dp[j-A[i]]+B[i])

	print(dp[H])

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

def main():
	H, N = MAP()
	A, B = [0]*N, [0]*N
	for i in range(N):
		A[i], B[i] = MAP()

	dp = [[INF]*(H+1) for _ in range(N+1)]
	dp[0][0] = 0


	for i in range(N):
		for j in range(H+1):
			if j < A[i]:
				dp[i+1][j] = min(dp[i][j], B[i])
			if j>= A[i]:
				dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i]]+B[i])
			

	#for i in range(N+1):
	#	print(dp[i])

	print(dp[N][H])

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def dp(H, N, ab):
  max_a = max([ab[i][0] for i in range(N)])
  d = [INF for _ in range(H + max_a)]
  d[0] = 0
  for h in range(1, H + max_a):
    d[h] = min(d[h - a] + b for a, b in ab)
  return min(d[H:])
INF = 10 ** 10
H, N = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(N)]
print(dp(H, N, ab))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

H,N = map(int,readline().split())
m = map(int,read().split())
AB = zip(m,m)

INF = 10 ** 18
U = 20000
dp = np.full(U, INF, np.int64)
dp[0] = 0

for a,b in AB:
    n = (U + (-U) % a) // a
    dp = np.resize(dp, U + (-U) % a).reshape(-1,a)
    dp -= (np.arange(n) * b)[:,None]
    dp = np.minimum.accumulate(dp, axis=0)
    dp += (np.arange(n) * b)[:,None]
    dp = dp.ravel()[:U]

answer = min(dp[H:])
print(answer)

Submission status: Accepted

Solution code:
H, N = map(int,input().split())
Magic = [list(map(int, input().split())) for i in range(N)]
MAX_COST = max(Magic)[1]

dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in Magic:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)
 
print(dp[-1])

Submission status: Accepted

Solution code:
h, n = map(int, input().split())
magics = [list(map(int, input().split())) for _ in range(n)]
max_a = max(a for a, b in magics)
dp = [0] * (h + max_a)
for i in range(1, h + max_a):
    dp[i] = min(dp[i - a] + b for a, b in magics)
print(dp[h])

Submission status: Accepted

Solution code:
h,n = map(int,input().split())
len = h + 10005
inf = 1000000000
res = inf
dp = [inf] * len
dp[0] = 0
for i in range(n):
    a,b = map(int,input().split())
    for j in range(len):
        if j >= a:
            dp[j] = min(dp[j],dp[j-a] + b)
        if j >= h:
            res = min(res,dp[j])
print(res)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
dmg = []
cost = []

for i in range(m):
    a, b = map(int, input().split())
    dmg.append(a)
    cost.append(b)

inf = 10**9
dp = [inf] * 30000
dp[0] = 0

for i in range(m):
    for j in range(n):
        if dp[j] != inf:
            dp[j + dmg[i]] = min(dp[j + dmg[i]], dp[j] + cost[i])
print(min(dp[n:]))

Submission status: Accepted

Solution code:
import numpy as np

h, n = map(int, input().split())
m = np.array([list(map(int, input().split())) for _ in range(n)])

max_a = np.max(m[:,0])
dp = np.zeros(h+max_a+1, dtype='i8')
for i in range(max_a+1, h+max_a+1):
    dp[i] = np.min(dp[i-m[:,0]] + m[:,1])
print(dp[h+max_a])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    H, N = map(int, input().split())
    A, B = [0] * N, [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    INF = 10**10  # INF+INFを計算してもオーバーフローしない範囲で大きく

    I, J = N, H
    # dpテーブル dp[i][j]:=i番目以下でjのダメージを与えるための最小コスト
    dp = [[INF]*(J+1) for _ in range(I+1)]
    # 初期条件
    for i in range(I):
        dp[i][0] = 0
    # ループ
    for i in range(I):
        for j in range(J+1):

            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            dp[i+1][min(j+A[i], J)] = min(dp[i+1]
                                          [min(j+A[i], J)], dp[i+1][j]+B[i])

    print(dp[I][J])


resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():


    H, N = map(int, input().split())
    A, B = [0] * N, [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    INF = 10**10  # INF+INFを計算してもオーバーフローしない範囲で大きく

    I, J = N, H
    # dpテーブル dp[i][j]:=i番目以下でjのダメージを与えるための最小コスト
    dp = [[INF]*(J+1) for _ in range(I+1)]
    # 初期条件
    for i in range(I):
        dp[i][0] = 0
    # ループ
    for i in range(I):
        for j in range(J+1):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            dp[i+1][min(j+A[i],J)] = min(dp[i+1][min(j+A[i],J)], dp[i+1][j]+B[i])
            
            
    print(dp[I][J])


resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    H, N = map(int, input().split())
    A, B = [0] * N, [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    INF = 10**10  # INF+INFを計算してもオーバーフローしない範囲で大きく

    I, J = N, H
    # dpテーブル dp[i][j]:=i番目以下でjのダメージを与えるための最小コスト
    dp = [[INF]*(J+1) for _ in range(I+1)]
    # 初期条件
    for i in range(I):
        dp[i][0] = 0
    # ループ
    for i in range(I):
        for j in range(J+1):
            # i番目を使うときでも使わないときでも
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            # 使うとき特有
            dp[i+1][min(j+A[i], J)] = min(dp[i+1][min(j+A[i], J)], dp[i+1][j]+B[i])
    print(dp[I][J])


resolve()

Submission status: Accepted

Solution code:
hh,n = map(int,raw_input().split(' '))
spells = [map(int, raw_input().split(' ')) for _ in range(n)]
h = [+float('inf')] * (hh+1)
h[0] = 0
for health in range(1, hh+1):
	for u,v in spells: h[health] = min(h[health], h[max(0,health - u)] + v)

print h[hh]

Submission status: Accepted

Solution code:
hh,n = map(int,raw_input().split(' '))
spells = [map(int, raw_input().split(' ')) for _ in range(n)]
h = {}
h[0] = 0

#h[health] = cost in points
for health in range(1, hh+1):
	for u,v in spells:
		h[health] = min(h[health] if health in h else +float('inf'), h[max(0,health - u)] + v)

print h[hh]

Submission status: Accepted

Solution code:
h, n  = map(int, input().split())
dp = [None] * (h+10)
dat = []
for _ in range(n):
    a,b = map(int, input().split())
    dat.append([a,b])
dp[0] = 0
for i in range(h):
    if dp[i] is None:
        continue
    for j in range(len(dat)):
        a,b = dat[j]
        #print(i,dp[i],j,a,b)
        magic = b + dp[i]
        nextdp = i + a
        if nextdp > h:
            nextdp = h
        if dp[nextdp] is None:
            dp[nextdp] = magic
        else:
            dp[nextdp] = min(dp[nextdp], magic)
#print(dp[:200])
print(dp[h])

Submission status: Accepted

Solution code:
h,n=map(int,input().split())
ab=[list(map(int,input().split()))for _ in range(n)]
maxa=max([a for a,b in ab])
maxmp=pow(10,8)
dp=[maxmp]*(h+maxa) # dp[i]:ダメージをぴったりi与えるのに必要な最小魔力
dp[0]=0
for i in range(h+maxa):
  b=[dp[i-a]+b for a,b in ab if i-a>=0]
  dp[i]=min(dp[i],min(b)) if b else dp[i]
print(min(dp[h:]))

Submission status: Accepted

Solution code:
h,n=map(int,input().split())
ab=[list(map(int,input().split()))for _ in range(n)]
maxmp=pow(10,8)
dp=[maxmp]*(h+10000) # dp[i]:ダメージをぴったりi与えるのに必要な最小魔力
dp[0]=0
for i in range(h+10000):
  b=[dp[i-a]+b for a,b in ab if i-a>=0]
  dp[i]=min(dp[i],min(b)) if b else dp[i]
print(min(dp[h:]))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

H, N = getNM()
magic = []
for i in range(N):
    a, b = getNM()
    # AがATC,BがMP
    magic.append([a, b])

dp = [float('inf')] * (H + 1)
dp[0] = 0
# HP = iを削るための最小MP
for i in range(1, H + 1):
    for j in magic:
        if i < j[0]:
            dp[i] = min(dp[i], j[1])
        else:
            dp[i] = min(dp[i], dp[i - j[0]] + j[1])
print(dp[-1])

Submission status: Accepted

Solution code:
import numpy as np
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
np_ab = np.array(ab)
max_a = max(np_ab[:,0]) #最大攻撃力
dp = [0]*(h + max_a)

for i in range(1, h + max_a):
    dp[i] = min(dp[i - a] + b for a, b in ab)
print(min(dp[h:]))

Submission status: Accepted

Solution code:
H,N=map(int,input().split())
AB=[]
for i in range(N):
    AB.append(list(map(int,input().split())))
maxA=max(AB)[0]
#dp[i] 敵に合計iダメージを与えるのに必要な最小魔力量
dp=[float("inf")]*(H+maxA)
dp[0]=0
for i in range(H):
    for fire,cost in AB:
        dp[i+fire]=min(dp[i+fire],dp[i]+cost)

ans=min(dp[H:])
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict
INF = 10**9

def main():
    h, n = list(map(int,sys.stdin.readline().split()))
    magic = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
    #print(magic)
    max_a = max(a for a, b in magic)
    dp = [0] * (h + max_a + 1)
    for i in range(1, h + max_a):
        dp[i] = min(dp[i - a] + b for a, b in magic)
        #print(dp)
    print(dp[h])

    return 0

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
# import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    h, n = ns()
    d = [na() for _ in range(n)]

    mat = [INF for _ in range(h + 1)]

    mat[0] = 0
    for i in range(h):
        if mat[i] == INF:
            continue
        for a, b in d:
            if i + a < h + 1:
                mat[i + a] = min(mat[i + a], mat[i] + b)
            else:
                mat[h] = min(mat[h], mat[i] + b)

    print(mat[h])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,N=map(int,input().split())
A=[];B=[]
for i in range(N):
    a,b=map(int,input().split())
    A.append(a);B.append(b)
dp=[[-1 for i in range(H+1)] for i in range(N)]
dp[0][0]=0
for i in range(N):
    dp[i][0]=0
tmp=0
while True:
    if tmp>=H:
        break
    if dp[0][tmp]!=-1:
        if tmp+A[0]>H:
            dp[0][H]=dp[0][tmp]+B[0]
        else:
            dp[0][tmp+A[0]]=dp[0][tmp]+B[0]
    tmp+=1
for i in range(N-1):
    tmp=0
    for j in range(H+1):
        dp[i+1][j]=dp[i][j]
    while True:
        if tmp>=H:
            break
        if dp[i+1][tmp]!=-1:
            if tmp+A[i+1]>=H:
                dp[i+1][H]=min(dp[i+1][H],dp[i+1][tmp]+B[i+1])
            else:
                if dp[i+1][tmp+A[i+1]]==-1:
                    dp[i+1][tmp+A[i+1]]=dp[i+1][tmp]+B[i+1]
                else:
                    dp[i+1][tmp+A[i+1]]=min(dp[i+1][tmp]+B[i+1], dp[i+1][tmp+A[i+1]])
        tmp+=1
print(dp[N-1][H])

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


h, n = inpl()
data = [inpl() for i in range(n)]

dp = [[INF] * (h + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    for j in range(h + 1):
        unused = dp[i][j]
        used = dp[i][j - data[i][0]] + data[i][1] if j - data[i][0] >= 0 else data[i][1]
        reused = dp[i + 1][j - data[i][0]] + data[i][1] if j - data[i][0] >= 0 else INF
        dp[i + 1][j] = min(unused, used, reused)
ans = dp[n][h]
print(ans)
# for i in dp:
#     print(i)

Submission status: Accepted

Solution code:
#初見じゃ無理だった。DPを使う
#標準入力
import math
H, N = map(int, input().split())
AB = []
max_A = 0
for i in range(N):
    ab = list(map(int, input().split()))
    if max_A < ab[0] :
        max_A = ab[0]
    AB.append(ab)

 #DP
DP = [0] * (H + max_A)
for i in range(1, H + max_A ): #DP[i] の最小値を求めていく
    tmp_mini = 10 ** 8
    for j in range(N):
        if i - AB[j][0] >= 0:
            tmp = DP[i - AB[j][0]] + AB[j][1]
            if tmp_mini > tmp:
                tmp_mini = tmp
    DP[i] = tmp_mini
print(min(DP[H: H + max_A]))

Submission status: Accepted

Solution code:
#dp[j] ->最低でもj以上のダメージを与えるのに必要な魔力の最小値
#

H,N = map(int,input().split())
dp = [float("INF")]*(H+1)
dp[0] = 0
for i in range(N):
    A,B = map(int,input().split())
    for j in range(1,H+1):
        dp[j] = min(dp[j],dp[max(j-A,0)]+B)

print(dp[-1])

Submission status: Accepted

Solution code:
def solve(h,n,a,b):
    dp = [[0 for j in range(h+1)] for i in range(n+1)]

    for i in range(n):
        for j in range(h+1):
            if j <= a[i] and i == 0:
                dp[i+1][j] = b[i]
            elif i == 0:
                dp[i+1][j] = dp[i+1][j-a[i]]+b[i]
            elif j <= a[i]:
                dp[i+1][j] = min(dp[i][j],b[i])
            else:
                dp[i+1][j] = min(dp[i][j],dp[i+1][j-a[i]]+b[i])
    return dp[n][h]

h, n = map(int,input().split())
a = []
b = []

for i in range(n):
    ai,bi = map(int,input().split())
    a.append(ai)
    b.append(bi)

print(solve(h,n,a,b))

Submission status: Accepted

Solution code:
h , n = map(int,input().split())
maho = []
for i in range(n):
    a,b = map(int,input().split())
    maho.append((a,b))
dp = [10**8 for i in range(h+1)]
for i in range(1,h+1):
    for a,b in maho:
        if i <= a:
            dp[i] = min(dp[i],b)
        elif i > a:
            dp[i] = min(dp[i],dp[i-a]+b)

print(dp[h])

Submission status: Accepted

Solution code:
h,n=map(int,input().split())

ab=[]
dp=[10**9]*(10**5)

maxA=0
for _ in range(n):
    a,b=map(int,input().split())
    dp[a]=min(dp[a],b)
    maxA=max(maxA,a)
#print(dp)
#dp[a]は、相手にaダメージを与えるときの、消耗する自分の最小HP
result=10**9
for i in range(1,h+maxA):
    #print(i,"##########")
    for k in range(1,i//2+2):
        dp[i]=min(dp[i],dp[k]+dp[i-k])
    if i>=h:
        result=min(result,dp[i])
    #print(dp)
print(result)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    h,n=map(int,input().split())
    lis=np.array([list(map(int,input().split())) for _ in range(n)])
    a_max=np.max(lis[:,0])
    dp=np.zeros(h+a_max+1,int)
    for i in range(a_max+1,a_max+h+1):
        dp[i]=np.min(dp[i-lis[:,0]]+lis[:,1])
    print(dp[a_max+h])

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
mx = max([a for a,b in ab])
dp = [[float('inf')]*(H+1+mx) for _ in range(N+1)]
# i番目までの魔法を使った時にモンスターの体力をj減らすするのに必要な魔力の最少値
dp[0][0] = 0

for i in range(N):
  a, b = ab[i]
  for j in range(H+1+mx):
    if j - a >= 0:
      dp[i+1][j] = min(dp[i+1][j-a]+b, dp[i][j])
    else:
      dp[i+1][j] = dp[i][j]

ans = float('inf')
for i in range(H, H+mx+1):
  ans = min(ans, dp[N][i])
print(ans)

Submission status: Accepted

Solution code:


H,N = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())

INF = float("inf")
dp = [[INF for _ in range(H+1)] for _ in range(N+1)]
dp[0][0] = 0

# 個数制限なしナップザック
for i in range(N):
    for j in range(H+1):
        if A[i] > j:
            # オーバーキルも可能なので。
            dp[i+1][j] = min(dp[i][j], B[i])
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j - A[i]] + B[i])

print(dp[-1][-1])

Submission status: Accepted

Solution code:

#150E
from functools import lru_cache
import sys
sys.setrecursionlimit(200000)

H,N = map(int, input().split()) #H<=10**4,N<=10**3

AB_dict = dict() #A:Atack power, B:Consumption MP

for i in range(N): #N<=10**3
    A,B = map(int, input().split())
    if A not in AB_dict:
        AB_dict[A] = B
    else:
        if B < AB_dict[A]: #同じ攻撃力なら消費MPが少ない方を優先する
            AB_dict[A] = B

@lru_cache(maxsize=None)
def get_consumption_MP(HP): #HPを削るのに必要なMPを求める関数
    ans = 10**9 + 7
    
    for AB in AB_dict.items():
        A = AB[0]
        B = AB[1]
        
        if A >= HP:
            if B < ans:
                ans = B
        else:
            if B + get_consumption_MP(HP-A) < ans:
                ans = B + get_consumption_MP(HP-A)
                
    return ans
        
print(get_consumption_MP(H))

Submission status: Accepted

Solution code:
H,N = map(int,input().split())
T = []
for i in range(N):
    a,b = map(int,input().split())
    T.append([a,b])

M = max(T)[0]
dp = [10**9]*(H+M+1)
dp[0] = 0
for i in range(1,H+M+1):
    for j in range(N):
        if i - T[j][0] >= 0:
            dp[i] = min(dp[i],dp[i-T[j][0]]+T[j][1])

print(min(dp[H:H+M+1]))

Submission status: Accepted

Solution code:
import sys
h, n = map(int, input().split())
# A = [0] * n
# B = [0] * n
AB = [list(map(int, input().split())) for _ in range(n)]
# for i in range(n):
#     A[i], B[i] = map(int, input().split())
min_hp = h
 
dp = [sys.maxsize] * (min_hp + 1)
dp[0] = 0
 
for i in range(0, min_hp + 1):
    for ab in AB: # type of spell
        next_index = min(i + ab[0], min_hp)
        dp[next_index] = min(dp[next_index], dp[i] + ab[1])
 
# dp = [[sys.maxsize] * (max_hp + 1) for i in range(n + 1)]
# for i in range(n + 1):
#     for j in range(min(A[1:]) + 1):
#         dp[i][j] = min(B[1:])
#
# for i in range(1, n + 1):
#     for j in range(1, max_hp + 1):
#         dp[i][j] = dp[i-1][j] if A[i] > j else min(dp[i-1][j-A[i]] + B[i], dp[i-1][j])
#         # dp[i][j] = dp[i][j-1] + B[i] if A[i] > j else min(dp[i][j-A[i]] + B[i], dp[i][j-1] + B[i])
print(dp[h])

Submission status: Accepted

Solution code:
import sys
h, n = map(int, input().split())
# A = [0] * n
# B = [0] * n
# for i in range(n):
#     A[i], B[i] = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
min_hp = h
max_hp = h + max(a for a, b in (AB))
 
dp = [sys.maxsize] * (max_hp + 1)
dp[0] = 0
 
for i in range(1, max_hp + 1):
    # dp[i] = min(dp[i - A[j]] + B[j] for j in range(n))
    dp[i] = min(dp[i - a] + b for a, b in AB)
print(min(dp[h:]))

Submission status: Accepted

Solution code:
import sys
h, n = map(int, input().split())
A = [0] * n
B = [0] * n
for i in range(n):
    A[i], B[i] = map(int, input().split())
min_hp = h
max_hp = h + max(A)
 
dp = [sys.maxsize] * (max_hp + 1)
dp[0] = 0
 
for i in range(1, max_hp + 1):
    dp[i] = min(dp[i - A[j]] + B[j] for j in range(n))
print(min(dp[h:]))

Submission status: Accepted

Solution code:
# coding: utf-8

H, N = (int(x) for x in input().split())

a = [0 for x in range(N)]
b = [0 for x in range(N)]
for i in range(N):
	a[i], b[i] = (int(x) for x in input().split())

inf = 10000000000
max_d = H + max(a)
dp = [[inf for x in range(max_d)] for x in range(N)]

dp[0][0] = 0

for i in range(N):
	for j in range(max_d):
		if i >= 1:
			dp[i][j] = min(dp[i][j], dp[i-1][j])
		if j - a[i] >= 0:
			dp[i][j] = min(dp[i][j], dp[i][j-a[i]] + b[i])

# for i in range(N):
# 	for j in range(max_d):
# 		if dp[i][j] == inf:
# 			print(" inf", end="")
# 		else:
# 			print("{0:>4}".format(str(dp[i][j])), end="")
# 	print("")

min_m = inf
for i in range(N):
	for j in range(max_d):
		if j >= H:
			min_m = min(min_m, dp[i][j])

print(min_m)

Submission status: Accepted

Solution code:
H, N = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N)]
dp = [float('inf')] * 10001
dp[0] = 0
for a, b in AB:
    for i in range(10001 - a):
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[H:]))

Submission status: Accepted

Solution code:
h, n = map(int, input().split())
inf = float("inf")

dp = [[inf]*(h+1) for i in range(n+1)]
dp[0][0] = 0

#dp[i][j] = i個目までの魔法を使って、ダメージの和をjにするときの最小コスト

for i in range(n):
  a, b = map(int, input().split())
  for j in range(h+1):  
    dp[i+1][j] = min(dp[i][j], dp[i+1][max(0, j-a)] + b)
"""
for i in range(n+1):
  print(dp[i])
"""
print(dp[n][h])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    h,n=map(int,input().split())
    lis=np.array([list(map(int,input().split())) for _ in range(n)])
    dp=np.zeros(h+1,int)
    dp[0]=0
    for i in range(1,h+1):
        dp[i]=np.min(dp[np.maximum(i-lis[:,0],0)]+lis[:,1])
    print(dp[h])

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    h,n=map(int,input().split())
    lis=np.array([list(map(int,input().split())) for _ in range(n)])
    dp=np.zeros(10**4+1,int)
    dp[0]=0
    for i in range(1,h+1):
        dp[i]=np.min(dp[np.maximum(i-lis[:,0],0)]+lis[:,1])
    print(dp[h])

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    h,n=map(int,input().split())
    lis=np.array([list(map(int,input().split())) for _ in range(n)])
    dp=np.zeros(10**4+1,int)
    dp[0]=0
    for i in range(1,h+1):
        dp[i]=np.min(dp[i-np.minimum(lis[:,0],i)]+lis[:,1])
    print(dp[h])

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    h,n=map(int,input().split())
    lis=np.array([list(map(int,input().split())) for _ in range(n)])
    dp=np.zeros(10**4+1,int)
    dp[0]=0
    for l in lis:
        dp[1:l[0]+1]=np.minimum(dp[1:l[0]+1],l[1])
    for i in range(1,h+1):
        dp[i]=np.min(dp[i-lis[:,0]]+lis[:,1])
    print(dp[h])

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
h, n = map(int, input().split())
# A = [0] * n
# B = [0] * n
# for i in range(n):
#     A[i], B[i] = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
min_hp = h
max_hp = h + max(a for a, b in (AB))

dp = [sys.maxsize] * (max_hp + 1)
dp[0] = 0

for i in range(1, max_hp + 1):
    # dp[i] = min(dp[i - A[j]] + B[j] for j in range(n))
    dp[i] = min(dp[i - a] + b for a, b in AB)
print(min(dp[h:]))