【題目描述】

潛水員為了潛水要使用特殊的裝備。他有一個(gè)帶2種氣體的氣缸：一個(gè)為氧氣，一個(gè)為氮?dú)狻Ｗ対撍畣T下潛的深度需要各種的數(shù)量的氧和氮。潛水員有一定數(shù)量的氣缸。每個(gè)氣缸都有重量和氣體容量。潛水員為了完成他的工作需要特定數(shù)量的氧和氮。他完成工作所需氣缸的總重的最低限度的是多少？

例如：潛水員有5個(gè)氣缸。每行三個(gè)數(shù)字為：氧，氮的（升）量和氣缸的重量：

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

如果潛水員需要5升的氧和60升的氮?jiǎng)t總重最小為249（1，2或者4，5號(hào)氣缸）。

你的任務(wù)就是計(jì)算潛水員為了完成他的工作需要的氣缸的重量的最低值。

【輸入】

第一行有2整數(shù)m，n（1≤m≤21，1≤n≤79）。它們表示氧，氮各自需要的量。

第二行為整數(shù)k（1≤n≤1000）表示氣缸的個(gè)數(shù)。

此后的k行，每行包括ai，bi，ci（1≤ai≤21，1≤bi≤79，1≤ci≤800）3整數(shù)。這些各自是：第i個(gè)氣缸里的氧和氮的容量及汽缸重量。

【輸出】

僅一行包含一個(gè)整數(shù)，為潛水員完成工作所需的氣缸的重量總和的最低值。

【輸入樣例】

5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

【輸出樣例】

249

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 1001 #define MOD 2520 #define E 1e-12 using namespace std; int m,n,k; int a[N],b[N],c[N],f[N][N]; void TwoDimensionPack(int weight_1,int weight_2,int cost) {for(int j=m;j>=0;j--){for(int k=n;k>=0;k--){int u=j+weight_1;int v=k+weight_2;if(u>=m)u=m;if(v>=n)v=n;f[u][v]=min(f[u][v],f[j][k]+cost);}} } int main() {cin>>m>>n>>k;for(int i=1;i<=k;i++)cin>>a[i]>>b[i]>>c[i];memset(f,INF,sizeof(f));f[0][0]=0;for(int i=1;i<=k;i++)TwoDimensionPack(a[i],b[i],c[i]);cout<<f[m][n]<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的潜水员（信息学奥赛一本通-T1271）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。