潜水员

题目描述

潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总量的最低限度是多少？

例如：潜水员有5个气缸。每行三个数字为：氧、氮的（升）量和气缸的重量：

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

如果潜水员需要5升的氧和60升的氮则总重最小为249（1,2或者4,5号气缸）

你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

输入描述

第一行有2整数m，n（1≤m≤21，1≤n≤79）。它们表示氧，氮各自需要的量。

第二行为整数k（1≤n≤1000）表示气缸的个数。

此后的k行，每行包括ai，bi，ci（1≤ai≤21，1≤bi≤79，1≤ci≤800）3整数。这些各自是：第i个气缸里的氧和氮的容量及气缸重量。

输出描述

仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。

样例输入

5 60

5

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

样例输出

129

代码详解

展开查看

m, n = [int(i) for i in input().split()]
k = int(input())
a = [0]
b = [0]
c = [0]
x = 0
y = 0

for i in range(1, k+1):
    ls = [int(i) for i in input().split()]
    a.append(ls[0])
    b.append(ls[1])
    c.append(ls[2])
dp = [[1061109567 for j in range(100)] for l in range(30)]

for i in range(1, k+1):
    for j in range(m, 0, -1):
        for l in range(n, 0, -1):
            if j<=a[i] & l<=b[i]:
                dp[j][l] = min(dp[j][l], c[i])
            else:
                if j-a[i]<0:
                    x = 0
                else:
                    x = j-a[i]
                if l-b[i]<0:
                    y = 0
                else:
                    y = l-b[i]
                dp[j][l] = min(dp[j][l], dp[x][y]+c[i])

print(dp[m][n])

运行结果

展开查看