uva 757 - Gone Fishing

点击打开链接uva 757

题目意思：

           john现有h个小时的空闲时间，他打算去钓鱼。john钓鱼的地方共有n个湖，所有的湖沿着一条单向路顺序排列（john每在一个湖钓完鱼后，他只能走到下一个湖继续钓）， john必须从1号湖开始钓起，但是他可以在任何一个湖结束他此次钓鱼的行程。

          john在每个湖中每5分钟钓的鱼数（此题中以5分钟作为单位时间），随时间的增长而线性递减。而每个湖中头5分钟可以钓到的鱼数以及每个湖中相邻5分钟钓鱼数的减少量，input中均会给出。并且John从任意一个湖走到它下一个湖的时间input中也都给出。求一种方案，使得john在有限的h小时中可以钓到尽可能多的鱼

解题思路：

1思路：贪心
2分析：
              1由于从湖1到最后一个湖的总时间是固定的，那么在扣除走路的时间后，我们可以认为这个人可以从一个湖“瞬间转移”到另外一个湖，即在任意时刻都能够从湖泊1到x中的任意一个掉一次鱼，我们以5分钟为一个单位。
              2那么我们就要去枚举这个人能够到达的湖从1-1，1-2，1-3......；然后对每一种情况求出当前能够调到的最多的鱼tmpAns和当前每一个湖所发的时间tmpTime，如果当前这种情况还有剩余时间没用完，那么直接加在tmpTime[0]上面。然后我们去判断当前tmpAns是否大于ans，如果是则更新ans并且更新ansTime；
              3输出有很多trick，第一如果ans为0，那么肯定把时间全部发在第一个湖，这个地方需要注意输出的情况。其它就是两个Case之间有空行，最后没有，然后“,”后有空格，最后一个没有。

代码：

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

int ans , n , h;
int f[MAXN] , d[MAXN] , t[MAXN];
int ansTime[MAXN];/*用来存储最后每个湖泊所发的时间*/

void solve() {
    int i , j , time , max , pos , tmpAns;
    int tmpTime[MAXN] , tmpF[MAXN];
    memset(ansTime , 0 , sizeof(ansTime));/*初始化为0*/
    for(i = 0 , ans = 0 ; i < n ; i++){
        time = 12*h - t[i];/*扣除走路的时间*/
        if(time <= 0) break;/*如果当前所剩time小于等于0都是不可能在到下一个湖的*/
        memcpy(tmpF , f , sizeof(f));/*数组复制*/
        tmpAns = 0 ; memset(tmpTime , 0 , sizeof(tmpTime));/*初始化*/
        while(1){
            if(!time) break;/*如果当前所剩time小于等于0都是不可能在到下一个湖的*/
            max = 0 ;
            for(j = 0 ; j <= i ; j++){
               if(max < tmpF[j]){
                   max = tmpF[j] ; pos = j;
               }   
            }
            if(!max) break;/*如果max为0，那么说明每一个湖鱼都为0，那么直接退出即可*/
            tmpAns += max ; tmpF[pos] -= d[pos];
            time-- ; tmpTime[pos]++;
        }
        if(time > 0) tmpTime[0] += time;/*如果还有剩时间则加在tmpTime[0]上面*/
        if(ans < tmpAns){/*判断ans是否小于tmpAns*/
            ans = tmpAns;
            memcpy(ansTime , tmpTime , sizeof(ansTime));
        }
    }
}

void output(){
    if(!ans) printf("%d" , h*60);/*如果ans为0，那么输出时候比较不同*/
    else printf("%d" , ansTime[0]*5);
    for(int i = 1 ; i < n ; i++)
        printf(", %d" , ansTime[i]*5);
    printf("\nNumber of fish expected: %d\n" , ans);
}

int main() {
    //freopen("input.txt", "r", stdin);
    int flag = 1;
    while(scanf("%d" , &n) && n){
        memset(t , 0 , sizeof(t));
        scanf("%d" , &h) ;
        for(int i = 0 ; i < n ; i++)
            scanf("%d" , &f[i]);
        for(int i = 0 ; i < n ; i++)
            scanf("%d" , &d[i]);
        for(int i = 1 ; i < n ; i++){
            scanf("%d" , &t[i]);
            t[i] += t[i-1];/*累加起来，方便计算*/
        }
        if(flag) flag = !flag;
        else printf("\n");
        solve() ; output();
    }
    return 0;
}