【动态规划】洛谷P1802 5 倍经验日(01背包问题)
2022/3/31 6:22:06
本文主要是介绍【动态规划】洛谷P1802 5 倍经验日(01背包问题),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一个洛谷普及-的题目,也是我刚刚入门学习动态规划的练习题。
下面发一下我的思路和代码题解:
我的思路及伪代码:
我的AC图:
接下来上代码:
1 //动态规划 洛谷P1802 五倍经验日 2 #include<iostream> 3 #include<cmath> 4 using namespace std; 5 struct human 6 { 7 int l;//失败 8 int w;//胜利 9 int u;//use 10 }hu[1005]; 11 long long ans[1005];//在主函数外 直接初始化为0 12 int main() 13 { 14 int n,x; 15 cin>>n>>x; 16 for(int i=1;i<=n;++i) 17 { 18 cin>>hu[i].l>>hu[i].w>>hu[i].u; 19 hu[i].w*=5;//注意题干!五倍经验 20 hu[i].l*=5; 21 } 22 for(int i=1;i<=n;++i)//外层循环 循环每一个use的值 23 { 24 for(int j=x;j>=hu[i].u;--j)//要从大遍历到小 注意! 25 { 26 ans[j]=max(ans[j]+hu[i].l,ans[j-hu[i].u]+hu[i].w);//状态转移方程 27 } 28 //本题特殊点 输了也有经验 所以有状态转移方程② 29 for(int j=hu[i].u-1;j>=0;j--)//注意是use[i]-1开始遍历 因为少的肯定输 30 { 31 ans[j]+=hu[i].l;//其实也用了贪心 少的直接一瓶药都不出 32 } 33 cout<<ans[x]; 34 } 35 return 0; 36 }
结束啦。
这篇关于【动态规划】洛谷P1802 5 倍经验日(01背包问题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南