题目链接:Click
here~~
题意:
一个人去钓鱼,在一条单向路上的旁边有n个湖,并且从湖i到湖i+1需要ti的时间,每个湖里面有fi条鱼,每钓一次鱼,鱼会减少di条。
在给定时间T内,问如何才能使钓的鱼最多,并记录在各个湖上停留的时间。
解题思路:
由于走路也需要耗费时间,所以为了争取更多的时间钓鱼,那个人肯定不会走回头路,即每条路花费的时间最多记1次,且剩下的时间即为钓鱼的时间。
所以,我们可以通过枚举他所到达的终点,来确定他路上所花费的时间,也就从而确定了钓鱼的时间。
确定钓鱼时间后,我们则可以根据贪心思想,每次选择鱼最多的那个湖进行钓鱼(因为耗费的时间是一样的)。
#include <queue>
#include <stdio.h>
#include <string.h>
#define bug puts("Ac???")
using namespace std;
struct Fish
{
int f,d,id;
bool operator < (const Fish& s)const
{
return f < s.f || f == s.f && id > s.id;
}
}A[30],R;
struct TT
{
int sum,t[30];
}ans,tmp,NEW;
int main()
{
int n,T,tt[30];
priority_queue <Fish> S;
for(int i=1;i<=25;i++)
A[i].id = i;
tt[1] = 0;
while(scanf("%d",&n),n)
{
ans = NEW;
ans.sum = -1;
scanf("%d",&T);
T *= 12;
for(int i=1;i<=n;i++)
scanf("%d",&A[i].f);
for(int i=1;i<=n;i++)
scanf("%d",&A[i].d);
for(int i=2;i<=n;i++)
{
scanf("%d",&tt[i]);
tt[i] += tt[i-1];
}
for(int j=1;j<=n;j++) //枚举终点
{
tmp = NEW;
for(int i=1;i<=j;i++)
S.push(A[i]);
for(int _t=1;_t <= T-tt[j];_t++)
{
R = S.top();
S.pop();
tmp.sum += R.f;
tmp.t[R.id] ++;
R.f -= R.d;
if(R.f < 0)
R.f = 0;
S.push(R);
}
if(tmp.sum > ans.sum)
ans = tmp;
while(!S.empty())
S.pop();
}
for(int i=1;i<n;i++)
printf("%d, ",ans.t[i]*5);
printf("%d\n",ans.t[n]*5);
printf("Number of fish expected: %d\n\n",ans.sum);
}
return 0;
}
分享到:
相关推荐
适合新手,详情可见我博客
爬虫地址:https://code.csdn.net/youqi1shi/ojrobot/tree/master nyoj的所有题目,每个问题都转化成了单独的网页,没有其他零碎内容。
NYOJ离线版.chm、北大ACM题库、北大ACM题解答
算法-矩形嵌套(NYOJ-16)(包含源程序).rar
双线程动态规划问题,很值得练习。传一个ac代码,测试一下csdn的功能。
经典算法,最大单调递增子序列,查看最多能嵌入多少个矩形
字典树,Trie树,查找插入效率都很高的一种高级数据结构。
由于微信小程序没有方法可以获得当前用户所在城市的信息,所以需要调用方法来获取城市信息,用了两个方法去发送请求并返回城市信息 1. @Controller public class WechatLocationManager { private Logger logger ...
这个小程序的主要目的是为了用户用微信的用户信息登录后将用户信息授权存入自己的数据库中,这样以后每次微信登录得到的code 所得到的 openid 可以在项目的数据库中查到该用户的相关信息。 在测试的过程中,需要用户...
前期小程序开发只进行到根据微信用户登录获取的code 去微信的API去获取到该用户的openId和session_key,到了第二阶段,老大让我重写OAuthManager的代码来实现微信小程序和微信公众号平台获取用户信息的优化,即将...
南阳理工学院stl练习场全部ac代码!
南阳理工学院OJ第1版解题报告V1.0.pdf
给定一个由整数组成二维矩阵(r*c),现在需要找出它的一个子矩阵,使得这个子矩阵内的所有元素之和最大,并把这个子矩阵称为最大子矩阵。