题目地址
话说,这个题从去年就想写了。解题报告都看了不知道多少遍,一直没能写出来(鄙视一下自己)。今天下了决心一定要写出来,果然、、、、花了一番心思后,终于AC啦!啦啦啦 嘿嘿 。。。吖飒!加油~~~~
题意(英文题,当初翻译了好久才明白题意,痛心呀,My English):
佳佳去钓鱼,池塘在一条直线上,每个池塘能钓到的鱼按di递减,从池塘i到i+1需要ti的时间。问佳佳最多能钓到的鱼。如果在池塘1和在池塘i+1钓的鱼数目一致,则佳佳就呆在池塘1。
分析:
大致的看看,并不能发现它是个贪心,或者,尽管知道它是贪心,并不能很好的分析出它的做题思路。
每个池塘能钓到的鱼数是递减的,从池塘i到i+1需要ti的时间。那么就可以,总时间先减去奔波各个池塘的时间。那么,就可以真正的贪心了(解题报告上就这一句话)。
如何贪心呢?今天才算知道、、、、、
因为会出现:最后j个池塘不值得去(路上花的时间不如去钓到别的池塘的鱼),解决这种冲突的办法就是,从前往后,搜索只去前i个池塘的Maxfish,记录最大Maxfish就是所求。至于在每个池塘所呆的时间,需要每次找到最优的Maxfish都更新一下。另外,把最后剩余的时间全部送给T[1]
#include<iostream>
#include <string.h>
using namespace std;
struct fish
{
int f;
int d;
int t;
}N[26];
int T[26];//每个湖停留的时间
int temp[26];
int Maxfish;int Troad;
int scheme(int n,int h)//前n个湖的最优方案
{
int i;int troad=0;
int sum=0;
int tt[26]={0};
memset(tt,0,sizeof(tt));
for(i=1;i<n;i++)
troad+=N[i].t;//实现0跳跃
h-=troad;
while(h>0)
{
//找鱼最多的湖
int m=0;int p;int flag=0;
for (i=1;i<=n;i++) if(N[i].f>m) {m=N[i].f;p=i;flag=1;}
if(flag==0) break;
sum+=m;tt[p]++;N[p].f-=N[p].d;
h--;
}
if(h>0) tt[1]+=h;
if(Maxfish<sum)
{
Troad=troad;Maxfish=sum;
for(i=1;i<=n;i++) T[i]=tt[i];
}
return 0;
}
int main()
{
int i,j;
int n;//湖的数量
while(cin>>n&&n!=0)
{
Maxfish=0;
memset(N,0,sizeof(N));
memset(T,0,sizeof(T));//忘记初始化,WA了两次。
int h;
cin>>h;//总的时间
h*=12;
for(i=1;i<=n;i++)
cin>>N[i].f;//最开始能钓到的鱼数
for(i=1;i<=n;i++)
cin>>N[i].d;//每分钟的减少量
for(i=1;i<n;i++)
cin>>N[i].t;//从i到i+1需要的时间间隔
//计算Maxfish及T[i]
for (i=1;i<=n;i++)//找最优方案
{
for(j=1;j<=n;j++)
temp[j]=N[j].f;
scheme(i,h);
for(j=1;j<=n;j++)
N[j].f=temp[j];
}
//print result
for(i=1;i<n;i++)
cout<<T[i]*5<<", ";
cout<<T[i]*5<<endl;
cout<<"Number of fish expected: "<<Maxfish<<endl;
cout<<endl;
}
return 0;
}
分享到:
相关推荐
算法-矩形嵌套(NYOJ-16)(包含源程序).rar
适合新手,详情可见我博客
爬虫地址:https://code.csdn.net/youqi1shi/ojrobot/tree/master nyoj的所有题目,每个问题都转化成了单独的网页,没有其他零碎内容。
NYOJ离线版.chm、北大ACM题库、北大ACM题解答
双线程动态规划问题,很值得练习。传一个ac代码,测试一下csdn的功能。
经典算法,最大单调递增子序列,查看最多能嵌入多少个矩形
字典树,Trie树,查找插入效率都很高的一种高级数据结构。
由于微信小程序没有方法可以获得当前用户所在城市的信息,所以需要调用方法来获取城市信息,用了两个方法去发送请求并返回城市信息 1. @Controller public class WechatLocationManager { private Logger logger ...
这个小程序的主要目的是为了用户用微信的用户信息登录后将用户信息授权存入自己的数据库中,这样以后每次微信登录得到的code 所得到的 openid 可以在项目的数据库中查到该用户的相关信息。 在测试的过程中,需要用户...
前期小程序开发只进行到根据微信用户登录获取的code 去微信的API去获取到该用户的openId和session_key,到了第二阶段,老大让我重写OAuthManager的代码来实现微信小程序和微信公众号平台获取用户信息的优化,即将...
给定一个由整数组成二维矩阵(r*c),现在需要找出它的一个子矩阵,使得这个子矩阵内的所有元素之和最大,并把这个子矩阵称为最大子矩阵。
南阳理工学院stl练习场全部ac代码!
南阳理工学院OJ第1版解题报告V1.0.pdf