题目描述
潜水员为了潜水要使用特殊的装备。
他有一个带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。它们表示氧,氮各自需要的量。
第二行为整数 k 表示气缸的个数。
此后的 k 行,每行包括ai,bi,ci,3个整数。这些各自是:第 i 个气缸里的氧和氮的容量及气缸重量。
输出格式
仅一行包含一个整数,为潜水员完成工作所需的气缸的重量总和的最低值。
数据范围
1≤m≤21,
1≤n≤79,
1≤k≤1000,
1≤ai≤21,
1≤bi≤79,
1≤ci≤800
样例
输入样例:
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
输出样例:
249
算法1
朴素版(三维)
状态表示和之前类似
不过这里要注意,遍历的过程中,气缸的氧气或者氮气含量可能为负数,为了不越界,我们令它们为0
f[i][j][k] = f[i-1][j][k];
f[j][k]=min(f[j][k],f[max(0,j-v1[i])][max(0,k-v2[i])]+w[i]);
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 24,M=80,K=1e3;
int n,m,o;
int f[K][N][M];
int v1[K], v2[K], w[K];
int main()
{
cin>>m>>o>>n;
memset(f,0x3f,sizeof f);
f[0][0][0]=0;
for (int i = 1; i <= n; i ++ )cin>>v1[i]>>v2[i]>>w[i];
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= m; j ++ )
for(int k = 0; k <=o ;k ++ )
{
f[i][j][k]=f[i-1][j][k];
f[i][j][k]=min(f[i][j][k],f[i-1][max(0,j-v1[i])][max(0,k-v2[i])]+w[i]);
}
cout <<f[n][m][o]<<'\n';
return 0;
}
算法2
优化到二维
不过要注意从大到小枚举就行
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 24,M=80,K=1e3;
int n,m,o;
int f[N][M];
int v1[K], v2[K], w[K];
int main()
{
cin>>m>>o>>n;
memset(f,0x3f,sizeof f);
f[0][0]=0;
for (int i = 1; i <= n; i ++ )cin>>v1[i]>>v2[i]>>w[i];
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= 0; j -- )
for(int k = o; k >=0 ;k -- )
{
f[j][k]=min(f[j][k],f[max(0,j-v1[i])][max(0,k-v2[i])]+w[i]);
}
cout <<f[m][o]<<'\n';
return 0;
}
算法3
输入优化
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 180;
int m,n,k;
int f[N][N];
int v1[N],v2[N],w[N];
int main()
{
cin>>n>>m>>k;
memset(f, 0x3f, sizeof f);
f[0][0]=0;
while(k--)
{
int v1,v2,w;
cin>>v1>>v2>>w;
for (int i = n; i >= 0; i -- )
for (int j = m; j >= 0; j -- )
f[i][j] = min(f[i][j], f[max(0, i - v1)][max(0, j - v2)] + w);
}
cout<<f[n][m]<<'\n';
return 0;
}