南京网络推广建站,课程建设网站设计源码,昆明网站建设推广服务,f2fpay wordpress有 N 个鱼塘排成一排#xff0c;每个鱼塘中有一定数量的鱼#xff0c;例如#xff1a;N5 时#xff0c;如下表#xff1a;
鱼塘编号12345第1分钟能钓到的鱼的数量 #xff08;1…1000#xff09;101420169每钓鱼1分钟钓鱼数的减少量#xff08;1…100)24653当前鱼塘到…有 N 个鱼塘排成一排每个鱼塘中有一定数量的鱼例如N5 时如下表
鱼塘编号12345第1分钟能钓到的鱼的数量 1…1000101420169每钓鱼1分钟钓鱼数的减少量1…100)24653当前鱼塘到下一个相邻鱼塘需要的时间单位分钟3544
即在第 1 1 1 个鱼塘中钓鱼第 1 1 1 分钟内可钓到 10 10 10 条鱼第 2 2 2 分钟内只能钓到 8 8 8 条鱼……第 5 5 5 分钟以后再也钓不到鱼了。
从第 1 1 1 个鱼塘到第 2 2 2 个鱼塘需要 3 3 3 分钟从第 2 2 2 个鱼塘到第 3 3 3 个鱼塘需要 5 5 5 分钟……
给出一个截止时间 T T T设计一个钓鱼方案从第 1 1 1 个鱼塘出发希望能钓到最多的鱼。
假设能钓到鱼的数量仅和已钓鱼的次数有关且每次钓鱼的时间都是整数分钟。
输入格式
共 5 5 5 行分别表示
第 1 1 1 行为 N N N
第 2 2 2 行为第 1 1 1 分钟各个鱼塘能钓到的鱼的数量每个数据之间用一空格隔开
第 3 3 3 行为每过 1 1 1 分钟各个鱼塘钓鱼数的减少量每个数据之间用一空格隔开
第 4 4 4 行为当前鱼塘到下一个相邻鱼塘需要的时间
第 5 5 5 行为截止时间 T T T。
输出格式
一个整数不超过 231 − 1 231−1 231−1表示你的方案能钓到的最多的鱼。
数据范围 1 ≤ N ≤ 100 1≤N≤100 1≤N≤100, 1 ≤ T ≤ 1000 1≤T≤1000 1≤T≤1000
输入样例
5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14输出样例
76#include iostream
#include algorithm
#include cstringusing namespace std;const int N 110;int a[N], d[N], l[N], spend[N];int get(int k) { //第i分钟在第k个鱼塘钓到鱼的数量return max(0, a[k] - d[k] * spend[k]);
}int work(int n, int T) { //只走前n个鱼塘且时间为T的最大收益int res 0;memset(spend, 0, sizeof spend);for (int i 0; i T; i ) { //按分钟遍历int t 1; //t表示第i分钟第t的鱼塘的鱼最多初始为1号鱼塘for (int j 1; j n; j ) //第i分钟在前n个鱼塘的最大收益if (get(j) get(t))t j;res get(t);spend[t] ; //在t号鱼塘逗留时间1}return res;
}int main() {int n, T; //n个鱼塘截止时间为Tcin n;for (int i 1; i n; i ) cin a[i]; //各鱼塘第一分钟产鱼量for (int i 1; i n; i ) cin d[i]; //各鱼塘每一分钟减鱼量for (int i 2; i n; i ) { //从第一个鱼塘到第i个鱼塘之间的距离cin l[i];l[i] l[i - 1]; //因为这步求前缀和所以前面下标i要从1开始}cin T;int res 0;for (int i 1; i n; i ) //从第一个鱼塘出发遍历n个鱼塘res max(res, work(i, T - l[i])); //只去前i个鱼塘的最大收益这里已经减去路上所用时间cout res endl;
}
