NYOJ Gone Fishing 贪心策略

Gone Fishing

时间限制：3000 ms | 内存限制：65535 KB

难度：5

描述

John is going on a fishing trip. He has h hours available (1 <= h <= 16), and there are n lakes in the area (2 <= n <= 25) all reachable along a single, one-way road. John starts at lake 1, but he can finish at any lake he wants. He can only travel from one lake to the next one, but he does not have to stop at any lake unless he wishes to. For each i = 1,…,n - 1, the number of 5-minute intervals it takes to travel from lake i to lake i + 1 is denoted ti (0 < ti <=192). For example, t3 = 4 means that it takes 20 minutes to travel from lake 3 to lake 4. To help plan his fishing trip, John has gathered some information about the lakes. For each lake i, the number of fish expected to be caught in the initial 5 minutes, denoted fi( fi >= 0 ), is known. Each 5 minutes of fishing decreases the number of fish expected to be caught in the next 5-minute interval by a constant rate of di (di >= 0). If the number of fish expected to be caught in an interval is less than or equal to di , there will be no more fish left in the lake in the next interval. To simplify the planning, John assumes that no one else will be fishing at the lakes to affect the number of fish he expects to catch.

Write a program to help John plan his fishing trip to maximize the number of fish expected to be caught. The number of minutes spent at each lake must be a multiple of 5.

输入

You will be given a number of cases in the input. Each case starts with a line containing n. This is followed by a line containing h. Next, there is a line of n integers specifying fi (1 <= i <=n), then a line of n integers di (1 <=i <=n), and finally, a line of n - 1 integers ti (1 <=i <=n - 1). Input is terminated by a case in which n = 0.

输出

For each test case, print the number of minutes spent at each lake, separated by commas, for the plan achieving the maximum number of fish expected to be caught (you should print the entire plan on one line even if it exceeds 80 characters). This is followed by a line containing the number of fish expected.

If multiple plans exist, choose the one that spends as long as possible at lake 1, even if no fish are expected to be caught in some intervals. If there is still a tie, choose the one that spends as long as possible at lake 2, and so on. Insert a blank line between cases.

样例输入

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

样例输出

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个湖，John可以在这个n个湖中穿行，ti*5表示第i个湖到i+1湖之间需要的时间间隔.fi表示第一次在每个湖中能钓到的鱼数，每在第i个湖钓一次 ，该湖中能掉到的鱼数就会减少di。需要求出John在时间60*h内就能钓到最多的鱼数目，以及在每个湖上话费的时间。

解题思路

很明显的贪心策略，假设John最后所在的湖为 x，我们可以发现在路上花费的时间60*h-tx，这些时间是完全用在钓鱼上，而不用考虑湖之间的距离，所以每一次钓鱼都可以在第0个湖到第x个湖之间选择每次可以钓到最多的湖进行钓鱼。只要枚举0~n能钓到鱼的数量，最后求最大值就可以啦。哈哈哈。

上代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;



int main()
{
    int num;
    while (~scanf("%d", &num) && num != ) {
        int h;
        cin >> h;
        int f[];
        int d[];
        int inter[];
        int i = ;
        for (; i < num; i++) {
            cin >> f[i];

        }
        //cout << "fi" << endl;
        /*for (i = 0; i < num; i++) {
            cout << f[i] << " ";
        }*/
    //  cout << endl;
        for (i = ; i < num; i++) {
            cin >> d[i];
        }
        /*cout << "di" << endl;
        for (i = 0; i < num; i++) {
            cout << d[i] << " ";
        }*/
        //cout << endl;
        int in;
        inter[] = ;
        for (i = ; i < num; i++) {
            cin >> in;
            inter[i] = inter[i - ] + in;
        }
        /*cout << "inter" << endl;
        for (i = 0; i < num; i++) {
            cout << f[i] << " ";
        }*/
        //cout << endl;
        int time = h * ;
        int fish_time[];
        for (i = ; i < num; i++) {
            fish_time[i] = time - inter[i] * ;
        }

        int ff[];
        i = ;
        int maxi = ;
        int fish[];
        for (i = ; i < num; i++) {
            int w;
            for (w = ; w < num; w++) {
                ff[w] = f[w];
            }
            fish[i] = ;
            int time_left = fish_time[i] / ;
            int k = ;
            for (; k < time_left; k++) {
                int j = ;
                int maxfi = ;
                int maxi = ;
                for (; j <= i; j++) {
                    if (maxfi < ff[j]) {
                        maxfi = ff[j];
                        maxi = j;
                    }
                }
                fish[i] += maxfi;
                ff[maxi] = ff[maxi] - d[maxi];
            }
        }
        i = ;
        int max = ;
        int lacki = ;
        for (; i < num; i++) {
            if (max < fish[i]) {
                max = fish[i];
                lacki = i;
            }
        }
        int lack_time[];
        for (i = ; i < num; i++) {
            lack_time[i] = ;
        }
        i = ;
        for (; i < num; i++) {
            ff[i] = f[i];
        }

        int time_left = fish_time[lacki] / ;
        int k = ;
        for (; k < time_left; k++) {
            int j = ;
            int maxfi = ;
            int maxi = ;
            for (; j <=lacki; j++) {
                if (maxfi < ff[j]) {
                    maxfi = ff[j];
                    maxi = j;
                }
            }
            ff[maxi] = ff[maxi] - d[maxi];
            lack_time[maxi] += ;
        }

        for (i = ; i < num; i++) {
            if (i == ) {
                cout << lack_time[i];
            }
            else
            {
                cout  << ", "<< lack_time[i];
            }           
        }
        cout <<endl<<"Number of fish expected: "<< max<<endl;
                 cout<<endl;
    }
    return ;
}

           

最后感谢一番

大概有一年多没有做过题了，本来就很水，现在更水。但是算法又相当重要，所以还是赶紧学习，刷一刷题吧。另外，我看了此题的标程，感觉自己的代码就是shi啊。说说标程的优点吧。值得学习。

1.封装性很好，不会像我一样把所有部分都一股脑的塞进main中，而是将要处理的部分封装到函数中，这样代码就很简介，漂亮，并且容易修改。

2.函数命名合理（哎，不多说，英语不好程序猿的都懂）。

3.使用库函数，往往比自己写的速度要快很多。

4.思路很清晰。

所以，任重而道远啊！！！