有n(2<=n<=25)个湖从左到右一字排开。从第i个湖走到第i+1个湖要耗时t[i]个时间片（每个时间片5分钟）。 John有h(1<=h<=16)个小时可以用在这些湖钓鱼（包括湖间行走时间）。在每个湖待的时间必须是整数个时间片或0。就算钓不着鱼了，也可以在湖边呆着。 对于湖i，John在那里的第一个时间片可以钓到鱼f[i]条，且后续的每个时间片，能钓到的鱼数量都比上一个时间片少d[i]。 注意John只能从第一个湖出发，从左往右走，不能回头。最后John要停在哪里都可以。问John最多能钓多少条鱼。
**输入： 每个测试用例，首先给出池塘数n，然后是时间h(小时为单位),接下来的两行分别有n个整数，分别表示f[i]和d[i],接下来的一行为n-1个整数，表示t[i]。n为0时表示输入结束。 输出： 对于每个测试用例，第一行依次输出在每个池塘的停留时间(分钟为单位)，每个时间之间用逗号+空格分开。第二行输出能钓到的最多的鱼的数量 ** Sample Input
2 1 10 1 2 5 2 4 4 10 15 20 17 0 3 4 3 1 2 3 4 4 10 15 50 30 0 3 4 3 1 2 3 0Sample Output
45, 5 Number of fish expected: 31 240, 0, 0, 0 Number of fish expected: 480 115, 10, 50, 35 Number of fish expected: 724这道题用的知识点是贪心、还有优先队列。 难点： 走路时间可多可少，不知道到底该花多长时间纯钓鱼才最好 解决： 枚举最终停下来的湖，将方案分成n类。每类方案的走路时间就是确定的。在每类方案里找最优解，然后再优中选优。终点是i 钓鱼时间=总时间-走路时间 钓鱼时间：钓鱼次数确定，每次都从f数组中找最大值。 如何找最大值。使用一个优先队列
优先队列的存储：
代码实现如下：
#include<iostream> #include<cstdio> #include<queue> using namespace std; int n, h, t[100010], fis[100010],time1[100010],d[100010]; typedef struct node { int fish, id, tim;//fish表示可以钓的鱼数，id表示当前的池塘号，tim表示停留时间。 bool operator < (const node & a)const { return fish == a.fish ? id > a.id:fish < a.fish; } //这个结构的意思是，定义的这三个量<a中的三个量。 //假如这两个的fish相等，就返回id小的的那个作为大的（题目要求）； //否则，就返回fish大的那个。 }node; void solve() { int maxn = -10000; int num; for (int i = 0; i < n; i++) {// 从第一个池塘开始枚举 priority_queue<node> q;//默认最大值在顶端，即树根，是按完全二叉树存的。 int time = h * 60;//输入的时间是小时，要转换成分钟。 time -= t[i] * 5; // 减去路程上花的时间 for (int j = 0; j <= i; j++) {//将枚举的池塘以此压入队列中 node next; next.fish = fis[j]; next.id = j;// 方便最后输出和排序 next.tim = 0; q.push(next); } int sum = 0; while (time > 0) { //在规定的时间内,吊枚举的池塘的鱼求出最大值,并求出来每个池塘的时间 node next = q.top(); q.pop(); sum += next.fish; next.tim += 5; time -= 5; if (next.fish) next.fish -= d[next.id]; if (next.fish < 0) next.fish = 0; q.push(next); } if (sum > maxn) {//判断是否是最大的 maxn = sum; num = i;//记录到哪个池塘鱼最多,之后的鱼塘停留的时间就是0; while (!q.empty()) { node next = q.top(); q.pop(); time1[next.id] = next.tim; } } } for (int i = 0; i <= num; i++) { if (i == 0) printf("%d", time1[i]); else printf(", %d", time1[i]); } for (int i = num + 1; i < n; i++) { printf(", 0"); } cout << endl; printf("Number of fish expected: %d\n", maxn); } int main() { while (scanf("%d", &n) && n) { scanf("%d", &h); for (int i = 0; i < n; i++) { cin >> fis[i];//表示池塘鱼数 } for (int i = 0; i < n; i++) { cin >> d[i];//表示钓过一次，减少多少鱼 } t[0] = 0; for (int i = 1; i < n; i++) { int x; cin >> x; t[i] = t[i - 1] + x;//这样储存的话就是到下标池塘的所需时间 } solve(); } return 0; }