`
人生难得糊涂
  • 浏览: 117416 次
社区版块
存档分类
最新评论

poj1042贪心钓鱼

 
阅读更多

题目大意:

一个人去钓鱼 ,有n个湖排成一行,他以第一个湖为起点,从一个湖到下一个湖需要 时间t[i]。第i个湖的鱼一开始每单位时间(以5分钟为单位)能钓上的鱼为f[i],每掉5分钟,则每个单位时间能掉上的鱼减少d[i]。求能掉上的最大的鱼的数目。以及在每个湖所呆的时间(可能有多个情况,要求的是尽量在一个湖呆长一点时间的情况)。

解题思路:假如我们走路不需要时间的话,那么这道题就变的简单了,直接用贪心策略,哪个湖现在每单位时间能钓的鱼数目最多,则在哪个湖钓。 

我们假设只在前i个湖钓鱼,那么我们走路的时间是不是可以求出来了。那么求出这个时间以后,用总时间减去走路时间就得到了能用与钓鱼的时间,在减去走路时间后,我们就可以在前i个湖之间直接“瞬移”(这个词也是在写完后看别人的解题报告中学到的,感觉很好理解),既然可以瞬移的话,我们每次选择现在单位时间能钓的最多的鱼的湖,在这个湖钓一个单位时间,鱼总数增加,这个湖单位时间能掉的鱼减少,然后我们再次 选择单位时间可以钓最多的湖,。。。(循环)。。。。。

 

可以结合着代码看。

 

 

#include<iostream>
using namespace std;
#define len 110
int main()
{
	int n,h;//n表示湖的个数,h表示时间
	int f[len],d[len],t[len];//fi是每个湖的初始值,di是每5分钟减少的值,ti是从 湖i到湖i+1所用的时间
	int i,j;
	int tot[len];
	int wait[len][len];//wait[i][j]表示第i个枚举中在第j个湖呆的时间
	while(true)
	{
	scanf("%d",&n);
	if(n==0)break;
	scanf("%d",&h);
	for(i=0;i<n;i++)
		scanf("%d",&f[i]);
	for(i=0;i<n;i++)
		scanf("%d",&d[i]);
	for(i=0;i<n-1;i++)
		scanf("%d",&t[i]);
	memset(tot,0,sizeof(tot));
	for(i=0;i<n;i++)
	memset(wait[i],0,sizeof(wait[i]));
	for(i=0;i<n;i++)//枚举只到前i个湖钓鱼
	{
		
		int tl=0;//从第0个湖走到第i个湖,走路所用总时间
		for(j=0;j<i;j++)
			tl+=t[j];
		int td=h*12-tl;//能用于钓鱼的时间=总时间-走路时间
		int a[len];
		for(j=0;j<=i;j++)//得到临时初始鱼欲望数组
		{
			
			a[j]=f[j];
		}
		
		for(;td>0;td--)//在时间用完之前
		{
			int max=0;
			int index=0;
			for(int k=0;k<=i;k++)//选一个最大下标
			{
				if(max<a[k])
				{
					max=a[k];
					index=k;
					
				}
			}
			wait[i][index]++;
			if(a[index]>=0)
			{
				
				tot[i]+=a[index];//在最大的这里掉一个单位时间的鱼
			}
			if(a[index]>=0)
				a[index]-=d[index];//钓鱼处减少
		}
	}
	int maxt=-99;
	int mindex=0;
	for(i=0;i<n;i++)
	{
		if(maxt<tot[i])
		{
			maxt=tot[i];
			mindex=i;
		}
	}
	for(i=0;i<n;i++)
	{
		cout<<wait[mindex][i]*5;
		if(i!=n-1)
		cout<<", ";
		else
			cout<<endl;
	}
	cout<<"Number of fish expected: "<<maxt<<endl;
	cout<<endl;
	}
	
	return 0;
}

 

 

1
0
分享到:
评论

相关推荐

    poj1087贪心算法实验报告

    在这个实验报告中,poj1087 题目就是一个典型的贪心算法应用实例。 题目描述了一个工厂需要将不同尺寸的产品(1*1 到 6*6)使用6*6的包裹进行包装,目标是最小化所需的包裹数量。贪心策略在此问题中的应用是逐个...

    田忌赛马: POJ 2287(贪心解法)

    《田忌赛马:POJ 2287 贪心解法解析》 在计算机科学领域,算法是解决问题的核心。"田忌赛马"这个题目来源于古代中国的一个著名故事,而在这个故事的基础上,被引入到了编程竞赛的场景中。POJ(Programming Online ...

    1050题目十.cpp

    北大POJ第1042题代码(C++)

    POJ 1129-Channel Allocation 的贪心算法解法(图的m着色问题)

    标题“POJ 1129-Channel Allocation”的问题是一个典型的图论问题,涉及到贪心算法和图的m着色问题。在这个问题中,我们假设有一个通信网络,其中的节点代表基站,每个基站需要分配一个频道来传输信号,而两个相邻的...

    POJ算法题目分类

    * 贪心:贪心算法是指通过选择当前最优的解来解决问题的方法,如 poj1328、poj2109、poj2586。 * 递归和分治法:递归和分治法是指将问题分解成多个小问题,通过解决小问题来解决大问题,如 poj3295。 * 递推:递推是...

    poj题目分类

    * 贪心算法:通过选择当前最优的解决方案来解决问题,例如 poj1328、poj2109、poj2586。 * 递归和分治法:通过将问题拆分成小问题来解决,例如 poj3295。 * 递推法:通过逐步解决问题来获得最终解,例如 poj1068...

    poj各种分类

    例如,poj1328和poj2109就是典型的贪心问题。贪心算法的关键在于正确性证明,确保每一步的局部最优能够导向全局最优。 #### 分治法与递归 分治法是将大问题分解成若干个子问题,递归地求解这些子问题,然后将子问题...

    POJ.rar_poj java_poj1048

    【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...

    poj训练计划.doc

    - 贪心算法:在每一步选择中都采取在当前状态下最好或最优的选择,如`poj1328, poj2109, poj2586`。 - 分治法:将一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,如`poj...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...

    POJ1010-STAMPS

    【标题】"POJ1010-STAMPS"是一个编程题目,来源于北京大学的在线判题系统POJ(Problem Set of Peking University),这是一处训练程序员算法技能和编程能力的平台。该题目旨在考察参赛者对动态规划或贪心算法的理解...

    POJ1201-Intervals

    代码中可能会用到动态规划、贪心算法等策略,以求在满足题目要求的同时,保证算法的时间复杂度尽可能低,从而在POJ平台上获得AC状态。而解题报告则会详细解释这些算法的应用和选择原因,以及代码的具体实现细节。

    POJ1159-Palindrome

    【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...

    POJ1840-Eqs

    7. **贪心策略**:在某些情况下,可以采用贪心算法,每次做出局部最优决策,最终达到全局最优。 8. **模拟**:有些题目可能需要编写程序来模拟现实世界的某些过程,例如模拟游戏规则或物理现象。 9. **位运算**:...

    POJ2503-Babelfish

    【标题】"POJ2503-Babelfish"是一个来自北京大学在线判题系统(POJ,Problem Online Judge)的编程题目。该题目要求参赛者编写程序解决特定的算法问题,通过编程语言实现,然后提交代码以供系统自动评测。 【描述】...

    POJ题目分析与理解

    1. 算法分类:POJ题目可以根据算法的难度和类型进行分类,例如,动态规划、贪心算法、递归算法等。 2. 题目分类:POJ题目可以根据题目类型进行分类,例如,数学题、字符串处理题、图算法题等。 3. 代码长度分类:POJ...

    POJ3122-Pie

    解题时,程序员可能需要理解问题背后的数学模型,然后选择合适的数据结构(如链表、队列、栈、树等)和算法(如动态规划、贪心、回溯等)来求解。例如,如果问题是关于分割圆饼,可能需要处理角度计算和分配的问题;...

    POJ2002-Squares

    【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...

    jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c

    标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...

Global site tag (gtag.js) - Google Analytics