Gone Fishing

       這道題其實難在讀題上，因為這道題的細節太多，往往容易搞混，造成WA的情況，所以，學好英語還是有作用的。

 

       解此題的主要方法是枚舉+貪心。剛開始的時候還沒想到一個好方法，因為當前魚最多的池塘是變化的，而題目所給描述里面的釣魚又是有順序的，即：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.所以，不可能在池塘中間瞬移，所以貪心貌似不能用。

 

       但轉念一想，瞬移還是有可能的，當確定了結束池塘ep（endpond）之后（結束池塘由1枚舉到n），我們便可以把從1到ep的交通費用從h中減去，然后用剩下的時間貪心即可。因為在分析問題時，對于一個池塘，John在它上面什么時候釣魚并不重要，所以可以先把John看成很聰明的人，然后假設他已經知道了在確定了結束池塘后，在每個池塘花多少時間使收益最大（實際上John是在貪心之后才知道的），這時我們就可以先減去交通費用，然后在1~ep的池塘中找現在的最大的即可。

 

       這道題還比較容易WA，但最容易WA的地方還是全零的情況。


#include <iostream>

using namespace std;
int const MAXP = 31;
int n, h, tt;
int f[MAXP], d[MAXP], t[MAXP];
int a[MAXP], res[MAXP];
int cf[MAXP];
int ans;

void initi() {
    fill(f, f+MAXP, 0);
    fill(d, d+MAXP, 0);
    fill(t, t+MAXP, 0);
    fill(a, a+MAXP, 0);
    fill(res, res+MAXP, 0);
    ans = -1;
}

int readIn() {
    int i, j;
    scanf("%d", &n);
    if (n == 0) return 0;
    scanf("%d", &h);
    tt = h * 12;
    for (i = 0; i < n; i++)
        scanf("%d", &f[i]);
    for (i = 0; i < n; i++)
        scanf("%d", &d[i]);
    for (i = 0; i < n-1; i++)
        scanf("%d", &t[i]);
    return 1;
}

void process() {
    int curtt, curfish;
    int i, j, ep; //    ep stands for end pond
    int tmpmf, tmpp;
    for (ep = 0; ep < n; ep++) {
        curtt = tt; curfish = 0;
        fill(a, a+MAXP, 0);
        for (i = 0; i < ep; i++) {
            curtt -= t[i];
            cf[i] = f[i];
        }
        cf[ep] = f[ep];
        
        for (i = 0; i < curtt; i++) {
            tmpmf = -1; tmpp = 0;
            for (j = 0; j <= ep; j++)
                if (tmpmf < cf[j]) {
                    tmpmf = cf[j];
                    tmpp = j;
                }
            a[tmpp]++;
            curfish += tmpmf;
            cf[tmpp] = max(0, cf[tmpp] - d[tmpp]);
        }
        
        if (curfish > ans) {
            ans = curfish;
            for (i = 0; i < n; i++) {
                res[i] = a[i];
            }
        }
    }
}

void printAns() {
    int i;
    for (i = 0; i < n; i++)
        res[i] *= 5;

    printf("%d", res[0]);
    for (i = 1; i < n; i++)
        printf(", %d", res[i]);
    printf("\n");
    printf("Number of fish expected: %d\n\n", ans);
}

int main() {
    initi();
    while (readIn()) {
        process();
        printAns();
        initi();
    }
    return 0;
}