本质是二维费用01背包问题
区别:初始化的时候要把除了0之外开成无穷
装的东西是可以大于背包容量的,所以要不上v1>i,v2>j的状态。
二维费用默认逆向循环
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int N=100;
int n,m,k;
int f[N][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]<<endl;
return 0;
}