题目1020. 潜水员题目描述潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸一个为氧气一个为氮气。让潜水员下潜的深度需要各种数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少例如潜水员有5个气缸。每行三个数字为氧氮的升量和气缸的重量3 36 120 10 25 129 5 50 250 1 45 130 4 20 119如果潜水员需要5升的氧和60升的氮则总重最小为24912或者45号气缸。你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。输入格式第一行有2个整数 mn。它们表示氧氮各自需要的量。第二行为整数 k 表示气缸的个数。此后的 k 行每行包括aibici3个整数。这些各自是第 i 个气缸里的氧和氮的容量及气缸重量。输出格式仅一行包含一个整数为潜水员完成工作所需的气缸的重量总和的最低值。数据范围1 ≤ m ≤ 21,1 ≤ n ≤ 79,1 ≤ k ≤ 1000,1 ≤ ai≤ 21,1 ≤ bi≤ 79,1 ≤ ci≤ 800时空限制1s / 64MB输入样例5 60 5 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119输出样例249思路特殊点j − v 1 [ i ] j-v1[i]j−v1[i]、k − v 2 [ i ] k-v2[i]k−v2[i]为负数怎么转移看成 0 就行。举个例子j − v 1 [ i ] j-v1[i]j−v1[i]为负数意思是不需要氧气了可以看成氧气为 0。初始化这里是取最小值因此将不可达的状态初始化为正无穷即可。对于所有的f [ 0 ] [ j ] [ k ] f[0][j][k]f[0][j][k]表示的是从前 0 个物品中选且氧≥ j ≥j≥j氮≥ k ≥k≥k的最小重量这些状态是不可达的初始化为正无穷。代码1三维数组#includebits/stdc.husingnamespacestd;constintN100010,M2110,K7910,INF0x3f3f3f3f;intn,V1,V2,v1[N],v2[N],w[N],f[N][M][K];intmain(){cinV1V2n;for(inti1;in;i)cinv1[i]v2[i]w[i];memset(f,0x3f,sizeoff);for(inti0;in;i)f[i][0][0]0;for(inti1;in;i)for(intj0;jV1;j)for(intk0;kV2;k)f[i][j][k]min(f[i-1][j][k],f[i-1][max(0,j-v1[i])][max(0,k-v2[i])]w[i]);coutf[n][V1][V2];return0;}代码2二维数组#includeiostream#includecstringusingnamespacestd;constintMaxV2110,MaxM7910;intN,V,M,f[MaxV][MaxM];intmain(){cinVMN;memset(f,0x3f,sizeoff);f[0][0]0;for(inti1;iN;i){intv,m,w;cinvmw;for(intjV;j0;j--){for(intkM;k0;k--){f[j][k]min(f[j][k],f[max(0,j-v)][max(0,k-m)]w);}}}coutf[V][M];return0;}结果
题目1020. 潜水员题目描述潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸一个为氧气一个为氮气。让潜水员下潜的深度需要各种数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少例如潜水员有5个气缸。每行三个数字为氧氮的升量和气缸的重量3 36 120 10 25 129 5 50 250 1 45 130 4 20 119如果潜水员需要5升的氧和60升的氮则总重最小为24912或者45号气缸。你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。输入格式第一行有2个整数 mn。它们表示氧氮各自需要的量。第二行为整数 k 表示气缸的个数。此后的 k 行每行包括aibici3个整数。这些各自是第 i 个气缸里的氧和氮的容量及气缸重量。输出格式仅一行包含一个整数为潜水员完成工作所需的气缸的重量总和的最低值。数据范围1 ≤ m ≤ 21,1 ≤ n ≤ 79,1 ≤ k ≤ 1000,1 ≤ ai≤ 21,1 ≤ bi≤ 79,1 ≤ ci≤ 800时空限制1s / 64MB输入样例5 60 5 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119输出样例249思路特殊点j − v 1 [ i ] j-v1[i]j−v1[i]、k − v 2 [ i ] k-v2[i]k−v2[i]为负数怎么转移看成 0 就行。举个例子j − v 1 [ i ] j-v1[i]j−v1[i]为负数意思是不需要氧气了可以看成氧气为 0。初始化这里是取最小值因此将不可达的状态初始化为正无穷即可。对于所有的f [ 0 ] [ j ] [ k ] f[0][j][k]f[0][j][k]表示的是从前 0 个物品中选且氧≥ j ≥j≥j氮≥ k ≥k≥k的最小重量这些状态是不可达的初始化为正无穷。代码1三维数组#includebits/stdc.husingnamespacestd;constintN100010,M2110,K7910,INF0x3f3f3f3f;intn,V1,V2,v1[N],v2[N],w[N],f[N][M][K];intmain(){cinV1V2n;for(inti1;in;i)cinv1[i]v2[i]w[i];memset(f,0x3f,sizeoff);for(inti0;in;i)f[i][0][0]0;for(inti1;in;i)for(intj0;jV1;j)for(intk0;kV2;k)f[i][j][k]min(f[i-1][j][k],f[i-1][max(0,j-v1[i])][max(0,k-v2[i])]w[i]);coutf[n][V1][V2];return0;}代码2二维数组#includeiostream#includecstringusingnamespacestd;constintMaxV2110,MaxM7910;intN,V,M,f[MaxV][MaxM];intmain(){cinVMN;memset(f,0x3f,sizeoff);f[0][0]0;for(inti1;iN;i){intv,m,w;cinvmw;for(intjV;j0;j--){for(intkM;k0;k--){f[j][k]min(f[j][k],f[max(0,j-v)][max(0,k-m)]w);}}}coutf[V][M];return0;}结果
