二维费用的变种
dp[i][j][k]表示所有从前i个物品中选,费用1恰好为j 费用2恰好为k的选法的最小值
体现在代码上就是让所有dp[0][j][k]=INF
处理完上述dp[][][]后,再枚举dp[N][>=V1][>=V2]的最小值即可
说明:普通二维费用问题中,dp[i][j][k]
表示从前i个物品中选,费用1<=j,费用2<=k的最大值,i=0时,dp[0][j][k]=0 是属于合法集合的
但是本题中不是合法方案,因为一个都不选时,体积不可能恰好==j或者k
应该定义为dp[0][j][k]=INF
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f
void print(int a[],int n){
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
}
const int N=50,M=160;
int dp[N][M];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int V1,V2;
cin>>V1>>V2;//表示氧气和氮气
memset(dp,0x3f,sizeof dp);
dp[0][0]=0;
int k;
cin>>k;
for(int i=1;i<=k;i++){
int v1,v2,w;
cin>>v1>>v2>>w;
for(int j=N-1;j>=0;j--)
for(int r=M-1;r>=0;r--)
dp[j][r]=min(dp[j][r],dp[max((int)0,j-v1)][max((int)0,r-v2)]+w);
}
int res=1e9;
for(int i=V1;i<N;i++)
for(int j=V2;j<M;j++)
res=min(res,dp[i][j]);
cout<<res<<endl;
return 0;
}