解题思路: 01 背包,f[i][j] 表示i氧j氮气瓶所需要的最小重量,(W) 重量维度优化省略, 因此以倒序遍历i,j
注意事项:当i - x 为负数时注意越界,因此取max(0,i-x)
参考代码:
#include<iostream> #include<algorithm> #include<cstring> using namespace std; int f[31][89],m,n,k,x,y,z; int main() { cin >> m >> n >> k; memset(f,0x3f, sizeof f); f[0][0] = 0; for(; k; k--){ cin >> x >> y >> z; for(int i = m; i >= 0; i --) for(int j = n; j >= 0; j --){ if(f[i][j]) f[i][j]=min(f[i][j],f[max(0,i-x)][max(0,j-y)] + z); } } cout << f[m][n]; return 0; }
0.0分
1 人评分