解题思路:
感谢地表最强召唤兽提供的代码,题目其实就是多重背包逆推
纵轴表示蛋糕的编号,横轴表示达到的美味度
不过要注意不是所有状态都是可以达到的,这是关键
更新当前一行的状态,然后再选择选或者不选当前蛋糕中较优的一种选择
注意事项:
参考代码:
#include<iostream> #include<algorithm> #include<algorithm> using namespace std; const int INF = 0x3FFFFFFF; int maxn = 50; int yami[50]; int cnt[50]; int sum[50][20010];//纵轴是蛋糕的编号,横轴表示当前美味度 int m, n; int main(void) { cin >> m >> n; for (int i = 0; i<n; i++) cin >> yami[i] >> cnt[i]; int sumn = 0;//蛋糕总数 for (int i = 0; i<n; i++) sumn += cnt[i]; for (int i = 0; i <= sumn; i++) { for (int j = 0; j <= m; j++) sum[i][j] = INF; } sum[0][0] = 0; int cur = 1; for (int i = 0; i<n; i++) { for (int j = 0; j<cnt[i]; j++) { for (int k = 0; k <= m; k++) { //k为可以获得的美味度和,k >= yami[i]表示达到的美味度和大于当前蛋糕的美味度 //sum[cur - 1][k - yami[i]] != INF表示当前美味度可以由之前的状态达到,关键! //sum[cur][k]>sum[cur - 1][k - yami[i]] + 1为选择最优的状态转移条件 if (k >= yami[i] && sum[cur - 1][k - yami[i]] != INF && sum[cur][k]>sum[cur - 1][k - yami[i]] + 1) { sum[cur][k] = sum[cur - 1][k - yami[i]] + 1; } } //选择或不选择当前蛋糕可以更优 for (int k = 0; k <= m; k++) { sum[cur][k] = min(sum[cur - 1][k], sum[cur][k]); } cur++; } } if (sum[cur - 1][m] != INF) cout << sum[cur - 1][m]; else cout << "><"; return 0; }
0.0分
2 人评分
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:658 |
求圆的面积 (C语言代码)浏览:1670 |
DNA (C语言描述,蓝桥杯)浏览:1555 |
1071题解浏览:493 |
单词个数统计 (C语言代码)浏览:1012 |
第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略浏览:1145 |
青年歌手大奖赛_评委会打分 (C语言代码)浏览:2149 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:771 |
小O的数字 (C++代码)浏览:763 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:699 |