题目传送

其实有一个更正经的题解

看了许久,发现这题貌似就是一个动态规划啊,但毕竟是贪心题库里的题,还是想想用贪心解吧。

经过(借鉴大佬思路)十分复杂的思考后,终于理解出了这题的贪心思路。该题的难点主要在最后可在任意湖边停住,而且不能往回走,在一个湖钓鱼时的效率还会越来越少。常规的思路看来是不行的了,题目好多动态未知的量,唯有我们更换角度,“化动为静”:

即然最后不知道停在哪个湖,那就分类讨论呗。把停在每个湖的最优解全部求出,在最后取个最优解不就行了吗?发现当我们知道主人公最后停在哪个湖后,她的路径也就唯一确定了(例如佳佳最后停在了第i个湖,那么她的路径一定是1—》2—》3—》。。。—》i),同时她的纯钓鱼时间可由总空闲时间减去行程时间唯一确定。考虑从哪个湖钓鱼一个5分钟,就相当于在路径1—》2—》3—》。。。—》i中的一个节点上“堆”上一个标记表示在这个湖又钓了5分钟的鱼,显然这里可用贪心策略,每次标记目前为止五分钟钓鱼数目最大的那个湖,并使当前记录答案的sumi+=在那个湖又钓的鱼数。最后比较所有的sumi(i=1,2,...,n)取最大的输出就行了。

还不懂?也许看看AC代码就懂了:

 #include<iostream>
#include<cstdio>
#include<cctype>
#include<vector>
using namespace std; int ans; vector<int>fish,lesss,t;//每个湖第一个 5 分钟能钓到鱼的数量,每个湖每钓鱼5分钟较前5分钟钓的鱼数减少的数量,如题意
vector<int>get,tmpfish;//从第一个湖走到第i个湖所需时间,每个湖的当前5分钟能钓到的鱼数 char ch; inline int read()//快读(亦名读入优化)
{
ans=;
ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) ans=(ans<<)+(ans<<)+ch-'',ch=getchar();
return ans;
} inline void init()//初始处理动态数组,因为希望动态数组的下标从1开始
{
fish.push_back();
lesss.push_back();
t.push_back();
get.push_back();
get.push_back();//注意get数组在主函数是从下标为2的开始处理的,因此需要多填一个0。
tmpfish.push_back();
}//为什么要填0?为了与普通全局数组的性质相同(定义时默认全初始化为0) int main()
{
init();
int n=read(),h=read()*;
for(int i=;i<=n;i++) fish.push_back(read());
for(int i=;i<=n;i++) lesss.push_back(read());
for(int i=;i<n;i++) t.push_back(read());
for(int i=;i<=n;i++) get.push_back(get[i-]+t[i-]);
int mava,mapo,tmphours,matot=;//当前贪心找到的最大值,当前贪心找到的最大值对应的下标(即湖的编号),当前纯钓鱼时间,最后的答案。
for(int i=;i<=n;i++) tmpfish.push_back();
for(int k=;k<=n;k++)
if(h>get[k])
{
tmphours=h-get[k];//可用的纯钓鱼时间
for(int i=;i<=k;i++) tmpfish[i]=fish[i];//初始化
int sum=;//记录的当佳佳最后停在第k个湖时的当前答案
while(tmphours>)
{
mava=-;
mapo=;
for(int i=;i<=k;i++)//贪心选择
if(mava<tmpfish[i])
{
mava=tmpfish[i];
mapo=i;
}
if(mava<=) break;//没鱼可钓就直接退出
sum+=mava;
if(tmpfish[mapo]>lesss[mapo]) tmpfish[mapo]-=lesss[mapo];
else tmpfish[mapo]=;
tmphours--;
}
if(sum>matot) matot=sum;
}
else break;
printf("%d",matot);
return ;
}

最后再总结一下贪心吧:

贪心策略的确定:看到题时,可根据生活经验(滑稽)确认一个直觉指引的贪心策略。对付简单题很有用。

        关注一下与题目有关的性质(可以是由数学推导的式子,或是题中描述的物品的一些跟生活有关的物理性质)基本跟贪心有关的题都会有找某个方面的最大值或最小值。

贪心策略的证明: 直接数学推导。

        假设有一个更优的方案,反证。

        玄学占卜

贪心的几点注意:当整体最优解可由局部最优解推出(并不只局限与一种策略)时才可用贪心。(否则用动态规划)

        基本能用贪心的动态规划都行,不过一般贪心的复杂度要优于动态规划。

最新文章

  1. oracle 数据库信息查询
  2. WAP端 穿透问题和解决方法
  3. iOS开发UI篇—Modal简单介绍
  4. 为什么html5用的jQuery Mobile在手机浏览器/微信中打开字体很小
  5. Box Anemometer
  6. 程序员的自我修养(2)——计算机网络(转) good
  7. codevs 3044 矩形面积求并 (扫描线)
  8. WindowsclientC/C++编程规范“建议”——前言
  9. Listener
  10. JQuery 纵向二级菜单与对齐方式
  11. 微信小程序发布
  12. 压测过程中,获取不到redis连接池,发现redis连接数高
  13. Unity项目导入的error
  14. 1804.03235-Large scale distributed neural network training through online distillation.md
  15. mysql windows开启客户端连接权限
  16. es 批量导入文件
  17. java正则表达式实战例子,持续更新,记下来后面就不用重新写了。。。
  18. Mac 10.12高级防火墙pfctl教程收集(待实践)
  19. 160414、java上传文件以流方式判断类型
  20. Web应用中使用JavaMail发送邮件进行用户注册

热门文章

  1. 堆排序 &amp;&amp; Kth Largest Element in an Array
  2. 关于MySQL的安装使用心得
  3. C语言中,当计算字符数组长度时,用sizeof 和strlen 的原理及两者的区别
  4. 首次全备及事务备份对数据库的影响,2014 SpexSql log评估版探索
  5. SQL如何通过当前日期获取上周一日期【转】
  6. P1168 中位数 堆
  7. POJ 3667 Hotel (线段树区间合并)
  8. GUI学习之十九——QFontComboBox学习总结
  9. impala常用语法
  10. VS2017报错:未提供初始值设定项