Gone Fishing

材料

题目来源 ：http://poj.org/problem?id=1042

题目文件 ：Gone Fishing题目.pdf

题意

约翰正在钓鱼。他有h小时的可用时间（1 <= h <= 16），并且该地区有n个湖泊（2 <= n <= 25）都可以通过一条单向路到达。约翰从1号湖开始，但是他可以在任何他想要的湖上结束。他只能从一个湖到另一个湖旅行，除非他愿意，否则他不必停在任何一个湖上。对于每个i = 1，…，n-1，从湖泊 i 到湖泊i + 1行驶5分钟的时间间隔表示为 ti（0 对于每个湖 i，已知在最初5分钟内将捕获的鱼的数量表示为 fi（fi> = 0）。每捕鱼5分钟，将以恒定的 di（di> = 0）的速率减少下一个5分钟间隔内预期捕获的鱼的数量。如果预计在一个间隔中捕获的鱼的数量小于或等于di，则在下一个间隔中湖中将不再有鱼。
为了简化计划，约翰假设其他人都不会在湖边钓鱼，以影响他希望捕捞的鱼的数量。
编写程序以帮助 John 计划他的钓鱼之旅，以最大程度地增加预期被捕捞的鱼类数量。
在每个湖泊上花费的分钟数必须是5的倍数。

输入格式

输入中将提供许多案例。 每个案例都以包含n的行开头。 这之后是包含h的行。 接下来，一行n个整数指定fi（1 <= i <= n），然后一行n个整数di（1 <= i <= n），最后一行一行n-1个整数ti（ 1 <= i <= n-1）。 输入在n = 0的情况下终止。

输出格式

对于每个测试用例，请打印每个湖所花费的分钟数，并用逗号分隔，以使计划达到预期的最大捕捞量 （即使计划超过80个字符，也应将整个计划打印在一行上） 这之后是一行，其中包含预期的鱼类数量。如果存在多个计划，则选择一个在湖1上花费尽可能长的计划，即使预计在一定间隔内不会捕获任何鱼类。 如果仍然有平局，请选择在2号湖上花费尽可能长的时间，依此类推。 在案例之间插入空白行

输入样例

2—————变量n ：代表湖泊数量 1—————变量h ：代表可用时间 10 1 ———变量fi : 代表最初5分钟内将捕获的鱼的数量 2 5 ———-变量di ：代表下一5分钟减少的鱼量 2 ————-变量ti : 代表每个湖间的路长

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

0

输出样例

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

解题思路

时间分为两部分

1. 在路上的时间
   • 花在路上的时间最多是从第一个池塘到最后一个池塘的时间
     • 名词解释：最后一个池塘指钓鱼次序中的最后一个池塘**，**而非真正实际中的最后一个池塘
2. 用于钓鱼的时间
   • 所以用总时间**减去从第一个池塘到最后一个池塘路上的时间，就是用于钓鱼的时间**

🚩如何求可能钓的最多的鱼？
**

1. 假设他从湖1 走到 湖X，则路上总共花了 T= T1 + T2 + T3 + … + Tx **，T=T-T**
2. 则可认为他能在1~X之间的任何两个湖之间 “ 瞬移 “，即任一时刻可任选一个1~X中的湖钓鱼
   • 举例子：
     • 假如先去湖1钓5分钟，接着去湖2钓5分钟，再回湖1钓5分钟，这个过程其实相当于先在湖1钓5+5=10分钟，然后再去湖2钓5分钟
3. 因此只需在1~X 的湖中一直贪心的选择当前能钓到鱼最多的湖即可
   • 备注：
     • 指的是1~X 中 fi [ **最初5分钟内将捕获的鱼的数量 **] 值最大，不要考虑的太复杂
4. 贪心选择的时候，若有多个相同 fi 的湖时，优先选择编号较小的湖
5. 上述步骤将会求解出从湖泊1**出发到湖泊X结束**所能钓的最大数量的鱼
6. 🦄显然最优解 X 必然等于1-n 中的某一个
7. 将 X 从 1 取到 n 搜索下，最后选个最优解即可

解题代码

优先队列处理

#include <algorithm>
#include <queue>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#pragma warning(disable:4996)//屏蔽vs的c不兼容错误
using namespace std;
const int maxn = 30;
struct node {
    int id;//湖泊编号
    int fi;//最初5分钟内将捕获的鱼的数量
    int di;//下一5分钟减少的鱼量
    int ti;//每个湖间的路长
    friend bool operator <(node a, node b) {   //从大到小排
        if (a.fi == b.fi) return a.id > b.id;  //若鱼数相等，则选择id较小的
        return a.fi < b.fi;
    }//重载 < 目的是为了方便优先队列内部排序, node本身不具备基础变量的比较关系 
};
node Lake[maxn];          //数组将会记录每个湖的信息
int times[maxn][maxn];    //记录每个湖钓鱼时间
int main() {
    int n, h;
    while (scanf("%d", &n) != EOF && n) {    //录入n
        scanf("%d", &h);                    //录入h时间
        memset(times, 0, sizeof(times));    //初始化，times数组全设置0
        h = h * 12;//1小时12个5分钟，即12片
        for (int i = 1; i <= n; i++) { scanf("%d", &Lake[i].fi); Lake[i].id = i; }
        for (int i = 1; i <= n; i++)   scanf("%d", &Lake[i].di);
        for (int i = 1; i <= n - 1; i++) scanf("%d", &Lake[i].ti);
        int maxans = 0;
        int maxk = 1;        //记录最终最优解X湖的id    
        for (int i = 1; i <= n; i++) {
            int tc = 0;        //tc计算路途时间
            for (int j = 1; j < i; j++) tc += Lake[j].ti;
            priority_queue<node> p;        //利用优先队列省略手动找最大fi的过程
            for (int j = 1; j <= i; j++) p.push(Lake[j]); //将湖1~i的鱼量放入从大到小排的优先队列
            int ans = 0;
            int t = h - tc;//t钓鱼时间
            for (int j = 1; j <= t; j++) {
                node foo = p.top();        //找到fi鱼最多的一个湖泊
                ans += foo.fi;             //ans保存当捕获最大值
                times[i][foo.id] += 5;    //保存i做结尾,1-i每个湖的钓鱼时间
                p.pop();
                //将刚才出队的结点信息更新入队
                p.push(node{ foo.id, max(foo.fi - foo.di, 0), foo.di });
            }
            if (maxans < ans) {//ans保存当前湖捕获最大值,maxans保存历来的最大值
                maxans = ans;
                maxk = i;
            }
        }
        for (int i = 1; i < n; i++) printf("%d, ", times[maxk][i]);
        printf("%d\n", times[maxk][n]);
        printf("Number of fish expected: %d\n\n", maxans);
    }
    return 0;
}

**