解题思路: 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 人评分
C二级辅导-进制转换 (C语言代码)浏览:514 |
K-进制数 (C++代码)浏览:853 |
时间转换 (Java代码)浏览:573 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:853 |
C语言程序设计教程(第三版)课后习题6.11 (C语言代码)浏览:549 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:630 |
矩阵加法 (C语言代码)浏览:1720 |
1231题解(注意理解“输入多个测试实例”)浏览:785 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:585 |
C语言程序设计教程(第三版)课后习题11.8 (C语言代码)浏览:992 |