题目大意:
Homer喜欢吃三明治,他吃Krusty三明治需要花m分钟,吃Kwik-e-Mart三明治需要花n分钟,现在给你t分钟,问Homer最多能吃几个三明治,若有剩余时间,则输出剩余时间,输出用空格隔开。
解题思路:
完全背包问题,相当于问t分钟能够由几个m和几个n凑成,之前有硬币凑钱的题目,问的就是使用给定的硬币,有几种方法能够凑到M元,这题类似,只是要算出共需几个m和n才能凑成t分钟,若凑不成,输出剩余时间。只需稍微改一下状态方程:
dp[j] = dp[ j - times[i] ]+1 > dp[j] ? dp[ j - times[i] ]+1 : dp[j];
dp[ j - times[i] ]+1表示,若times[i]能够凑成 j , 则dp[j] 就等于dp[ j - times[i] ]所需的硬币总数再加上 1 个硬币,且这个硬币就是times[i]。由于要求最大的,所以要和原来的dp[i]相比,取大者,比如15分钟,可以有3个5和5个3组成,则根据题目要求,应该取5个3。
代码:
#include <iostream> #include <cstring> #include <vector> #include <algorithm> using namespace std; long long dp[10010] = {0}; long long times[2] = {0}; int main() { long long m, n, t, beer; while( cin>>m>>n>>t ) { memset( dp, 0, sizeof( dp ) ); times[0] = m; times[1] = n; dp[0] = 1; for( int i = 0; i < 2; i++ ) { for( int j = times[i]; j <= t; j++ ) { if( dp[ j - times[i] ] ) { dp[j] = dp[ j - times[i] ]+1 > dp[j] ? dp[ j - times[i] ]+1 : dp[j]; } } } int tag = 0; for( int i = t; i >= 0; i-- ) { if( dp[i] ) { tag = i; beer = t - i; //求剩余时间 break; } } if( beer ) cout<<dp[tag]-1<<" "<<beer<<endl; else cout<<dp[tag]-1<<endl; } return 0; }
相关推荐
我们为您保存了著名的虚构人物荷马·辛普森(Homer Simpson)的背景。 扩展程序带有高清分辨率的高质量背景,将完全改变您的浏览器并赋予它完全不同的外观。 重要的是,每次您打开新标签页时都会显示该标签。 但这还...
HOMER的帮助文件和使用说明,英文版。 HOMER 微功耗优化模型简化了评估各种应用的离网和并网电力系统设计的任 务。在设计电力系统时,您必须对系统的配置作出许多决定:在系统设计中包含 哪些组件是有意义的?每个...
HOMER
HOMER仿真软件教程,网上的稀缺资源,七步让你掌握HOMER
HOMER Energy公司的HOMER Pro微电网软件是优化微电网设计的全球标准,适用于从乡村电力和岛屿公用事业到联网校园和军事基地的所有领域。HOMER(多能源混合优化模型)最初由国家可再生能源实验室开发的,并由HOMER ...
homer微网仿真软件
HOMER软件说明书中文版借鉴.pdf
什么是HOMER? HOMER微功耗优化模型简化了评估各种应用的离网和并网电力系统设计的任务。在设计电力系统时,您必须对系统的配置作出许多决定:在系统设计中包含哪些组件是有意义的?每个组件应该使用多少和什么尺寸...
光伏发电,HOMER软件实例工程
宏美电气 (HOMER)XMC6专用交流接触器pdf,宏美电气 (HOMER)XMC6专用交流接触器:超长电气耐久性:约定操作性能试验可达12万次(国标要求仅6000次)。可靠性高:经受大样本数量反复试验,全面通过考核指标。用户评价好:...
英文版本的Homer software指导,适合初学者。现在很难找到可以下载的Homer软件,如果有朋友有资源,麻烦共享一下软件
英文版本的homer入门手册。可以从其官网上下载。
homer(Hybrid Optimization Model for Electric Renewable,可再生能源互补发电优化建模)。homer是一个计算机模型,它简化了离网和并网对于远程的、独立的和分布式发电系统的评估选择的任务。homer优化和灵敏度分析...
HOMER is the global standard for microgrid optimization. Avoid costly mistakes by focusing on optimal hybrid power systems that meet your needs.
matlab开发-Homer2。分析功能性近红外光谱测量的工具。
用HOMER软件画出的某地区一年每小时的光照,将其导出为文本格式,可导入到MATLAB中供研究人员使用
Homer算法应用
HOMER是一套基于Bootstrap3+、HTML5和CSS3开发的响应式后台模板。它包含了主流可重用的UI组件并集成了一些最新的jQuery插件。可用于小型和中型WebApp。 该资源包包含以下模板项目包: Angular Full Version (Grunt/...
用HOMER软件画出的某地区一年每小时的风速,将其导出为文本格式,可导入到MATLAB中供研究人员使用
HOMER软件说明书中文版资料.pdf