学生个人网站模板,wordpress产品自定义增加列,网站提升收录,有做淘宝网站的题目描述#xff1a;
有 N 个鱼塘排成一排#xff0c;每个鱼塘中有一定数量的鱼#xff0c;例如#xff1a;N5 时#xff0c;如下表#xff1a;
鱼塘编号12345第1分钟能钓到的鱼的数量#xff08;1..1000#xff09;101420169每钓鱼1分钟钓鱼数的减少量#xff08;1…题目描述
有 N 个鱼塘排成一排每个鱼塘中有一定数量的鱼例如N5 时如下表
鱼塘编号12345第1分钟能钓到的鱼的数量1..1000101420169每钓鱼1分钟钓鱼数的减少量1..100)24653当前鱼塘到下一个相邻鱼塘需要的时间单位分钟3544
即在第 1 个鱼塘中钓鱼第 1 分钟内可钓到 10 条鱼第 2 分钟内只能钓到 8 条鱼……第 5 分钟以后再也钓不到鱼了。
从第 1个鱼塘到第 2 个鱼塘需要 3 分钟从第 2 个鱼塘到第 33 个鱼塘需要 5 分钟……
给出一个截止时间 T设计一个钓鱼方案从第 1 个鱼塘出发希望能钓到最多的鱼。
假设能钓到鱼的数量仅和已钓鱼的次数有关且每次钓鱼的时间都是整数分钟。
输入格式
共 5 行分别表示
第 1行为 N
第 2行为第 1分钟各个鱼塘能钓到的鱼的数量每个数据之间用一空格隔开
第 3行为每过 1 分钟各个鱼塘钓鱼数的减少量每个数据之间用一空格隔开
第 4 行为当前鱼塘到下一个相邻鱼塘需要的时间
第 5 行为截止时间 。
输出格式
一个整数不超过231−1231−1表示你的方案能钓到的最多的鱼。
数据范围
1≤N≤100, 1≤T≤1000
输入样例
5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14输出样例
76 解题思路
每个鱼塘的数量随着时间的流逝相当于一个等差数列。可以将所有鱼塘数量放在一个集合中每次取最大值。但每次更换鱼塘都会花费走路的时间。可以枚举只从前1-n1nN个鱼塘中钓鱼 这样走路花费的时间就一定剩下的T-time则可以用来从前n个鱼塘构成的等差数列中每次选择最大数。 参考代码
#include iostream
#include cstring
#include algorithmusing namespace std;
const int N 110;
int a[N],d[N],speed[N],l[N];
int n;int get(int x)
{return max(0,a[x] - d[x] * speed[x]);
}int work(int n,int T)
{memset(speed,0,sizeof speed);int res 0;for(int i0;iT;i){int t 1;for(int j2;jn;j)if(get(t)get(j))t j;res get(t);speed[t];}return res;
}int main()
{cinn;for(int i1;in;i) cina[i];for(int i1;in;i) cind[i];for(int i2;in;i){cinl[i];l[i] l[i-1];}int T;cinT;int res 0;for(int i1;in;i){res max(res,work(i,T-l[i]));}printf(%d\n,res);return 0;
}
