2138: 信息学奥赛一本通T1290-采药

解题思路:

注意事项:

参考代码:

m,n=map(int,input().split())
ls=[[0,0]]
for i in range(n):
    ls.append(list(map(int,input().split())))
dp=[[0 for i in range(m+1)] for j in range(n+1)]
for num in range(1,n+1):
    for wet in range(1,m+1):
        if wet < ls[num][0]:
            dp[num][wet]=dp[num-1][wet]
        else:
            value_max=ls[num][1]+dp[num-1][wet-ls[num][0]]
            dp[num][wet]=max(dp[num-1][wet],value_max)
print(dp[-1][-1])