AcWing 1020. 潜水员(至少)
原题链接
简单
作者:
半透明の微笑
,
2024-04-08 15:30:26
,
所有人可见
,
阅读 4
//至少最多恰好各种情况大佬解析:https://www.acwing.com/solution/content/7438/
import java.io.*;
import java.util.*;
public class Main{
static int N = 1010;
static int M = 110;
static int[] a = new int[N];
static int[] b = new int[N];
static int[] c = new int[N];
static int[][] f = new int[M][M];
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str1 = br.readLine().split(" ");
int m = Integer.parseInt(str1[0]);
int n = Integer.parseInt(str1[1]);
int t = Integer.parseInt(br.readLine());
for(int i = 1; i <= t; i ++){
String[] str2 = br.readLine().split(" ");
a[i] = Integer.parseInt(str2[0]);
b[i] = Integer.parseInt(str2[1]);
c[i] = Integer.parseInt(str2[2]);
}
for(int i = 0; i <= m; i ++) Arrays.fill(f[i],0x3f3f3f3f);
f[0][0] = 0;
for(int i = 1; i <= t; i ++){
for(int j = m; j >= 0; j --){
for(int k = n; k >= 0; k --){
//f[i][j]:表示"至少"获得i升氧气且"至少"获得j升氮气的所有情况下,气缸的最小值
//是可以从负数转移过来的
f[j][k] = Math.min(f[j][k], f[Math.max(0, j - a[i])][Math.max(0, k - b[i])] + c[i]);
}
}
}
System.out.println(f[m][n]);
}
}