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;
}