Coder Space

题意：在笔直的路边有一些池塘，从左到右编号为1,2...n。John共有H个小时的空余时间，他希望能钓到尽量多的鱼。他从池塘1出发，向右走，有选择的在一些池塘边停留一定的时间钓鱼，
            现已经测出John从第i个湖到第i+1个湖走路需要的时间5*Ti分钟，还测出在第i个湖边停留，第一个5分钟可以钓到的鱼Fi，以后每5分钟能钓到的鱼的数量减少Di.为简化问题假定没有
            其它因素会影响到他钓鱼的数量，要求出John能钓到最多鱼的方案。

解法：求出在h小时内可以走过的最大池塘数x，从1到x枚举，路上花费时间为t,用总时间减去t，剩下的是可用于钓鱼的总时间。
             每次钓鱼用贪心算法，找出鱼最多的池塘钓。找出1到x所有情况下钓鱼最多的方案即为所求。注意小细节。

源代码
  1#include<iostream>
  2
  3using namespace std;
  4
  5const int MAXN = 26;
  6
  7int f[MAXN];
  8int d[MAXN];
  9int t[MAXN];
 10int tF[MAXN];                 //f[]的备份，用于每次枚举
 11int resTime[MAXN];            //最好所求的每个池塘的钓鱼时间
 12int curTime[MAXN];            //每次枚举得到的钓鱼时间
 13
 14int getMaxFish(int n)         //求每个循环，最大鱼量的池塘及可钓得鱼量，并更新有关数组
 15{                             //若都不能获得鱼，则在1号池塘空呆
 16    int ind = 1;
 17    int maxF = -1;            //注意为-1,不能为0
 18    for(int i=1; i<=n; i++)
 19    {
 20        if(maxF < tF[i])
 21        {
 22            maxF = tF[i];
 23            ind = i;
 24        }
 25    }
 26    tF[ind] -= d[ind];
 27    if(tF[ind] < 0)           //负数时赋为0,表示不能钓到鱼，再不是损失鱼
 28    {
 29        tF[ind] = 0;
 30    }
 31    ++curTime[ind];
 32    return maxF;
 33}
 34
 35int main()
 36{
 37    int n,h;
 38    int n5m;                   //用分钟表示的时间
 39    int nLake,traTime;         //最多可走过的池塘及路上花费时间
 40    int curFish,maxFish;
 41
 42    cin>>n;
 43    while(n!=0)
 44    {
 45        cin>>h;
 46        for(int i=1; i<=n; i++)
 47        {
 48            cin>>f[i];
 49        }
 50        for(int i=1; i<=n; i++)
 51        {
 52            cin>>d[i];
 53        }
 54        for(int i=1; i<n; i++)
 55        {
 56            cin>>t[i];
 57        }
 58        n5m = h*12;
 59        traTime = 0;
 60        for(nLake = 1; nLake<n; nLake++)       //求最大可走到的池塘数
 61        {
 62            if(traTime + t[nLake] > n5m)
 63            {
 64                break;
 65            }
 66            traTime += t[nLake];
 67        }
 68
 69        for(int i=1; i<=n; i++)                //初始化
 70        {
 71            resTime[i] = 0;
 72        }
 73
 74        maxFish = -1;
 75        for(int i=1; i<=nLake; i++)            //求解过程
 76        {
 77            n5m -= t[i-1];
 78            curFish = 0;
 79
 80            for(int j=1; j<=i; j++)            //初始化
 81            {
 82                tF[j] = f[j];
 83                curTime[j] = 0;
 84            }
 85
 86            for(int j=1; j<=n5m; j++)          //每一轮可钓得的最大鱼量
 87            {
 88                curFish += getMaxFish(i);
 89            }
 90            if(curFish > maxFish)
 91            {
 92                maxFish = curFish;
 93                for(int j=1; j<=i; j++)
 94                {
 95                    resTime[j] = curTime[j];
 96                }
 97            }
 98        }
 99        cout<<resTime[1]*5;
100        for(int i=2; i<=n; i++)
101        {
102            cout<<", "<<resTime[i]*5;
103        }
104        cout<<"\nNumber of fish expected: "<<maxFish<<endl<<endl;
105        cin>>n;
106    }
107    return 0;
108}
109