POJ 1042

タイトル:
ジョンは釣りに行って、一方向の多くの湖の道端で釣りをして、湖ごとに5分ごとに釣れる魚の数は時間が経つにつれて減少して、湖ごとに歩く時間も違いますが、固定的に変わりません.質問は,合計時間h時間を与え,アルゴリズムを記述し,最も釣れる魚の解決策を求めることである.
入力:湖の数、与えられた総時間、各湖頭5分で釣れる数、各湖釣りの減衰速度、各2つの湖間の歩行時間
出力:湖ごとに釣りをする時間と、最大の釣りの数
分析:列挙アルゴリズムに欲張りアルゴリズムを加える
まず、どの案を選んでも、最後にジョンは最後に釣りをする湖があるに違いない.だから、最終案は以下の案の一つに違いない:i条湖で仕事を終える(i=1,2,3,4......n).
以上は列挙ですが、列挙のそれぞれのケースの後、次の5分間、どの湖で釣れる魚が一番多いかを見て、どの湖を選ぶか、「瞬時に移動」して、時間が尽きるまで続けます
これが欲張りアルゴリズムで、毎回最適な案を選択します.
負の数が現れたら、時間はすべて最初の湖に累加します.釣りが最も多い案が複数ある場合は、前のいくつかの湖の中で最も時間がかかるものを探せばいいです.
最後に注意したいのは、出力フォーマットです.(1つのスペースに長い間ACを使っていました)

#include<iostream>
#include<cstring>
#define MAX 26
using namespace std;

int t[MAX],f[MAX],F[MAX],d[MAX],ans[MAX],ANS[MAX]; //ANS             

int main(){
    int i,j,k,h,time,n,p,sum,max;
    memset(t,0,sizeof(t));
    while(cin>>n&&n!=0){
        cin>>h;
        h = h * 12;
        for(i=0;i<n;i++)
            cin>>F[i];
        for(i=0;i<n;i++)
            cin>>d[i];
        for(i=1;i<n;i++){
            cin>>time;
            t[i] = time + t[i-1];
        }
        memset(ANS,0,sizeof(ANS));
        for(max=0,i=1;i<=n;i++){
            memset(ans,0,sizeof(ans));
            for(k=0;k<i;k++)
                f[k] = F[k];
            for(sum=0,j=0;j<h-t[i-1];j++){
                for(p=0,k=1;k<i;k++){
                    if(f[k]>f[p])
                        p = k;
                }
                if(f[p]<=0){
                    ans[0]+= h - t[i-1] - j;
                    break;
                }
                sum += f[p];
                f[p] -= d[p];
                ans[p]++;
            }
            if(sum>max){
                max = sum;
                memcpy(ANS,ans,sizeof(ans));
            }
            if(sum == max){
                for(j=0;j<i;j++){
                    if(ans[j]!=ANS[j])
                        break;
                }
                    if(ans[j]>ANS[j]){
                        memcpy(ANS,ans,sizeof(ans));
                }
            }
        }
        for(i=0;i<n;i++){
            if(i==n-1){
                cout<<ANS[i]*5<<endl;
                break;
            }
            cout<<ANS[i]*5<<", ";
        }
        cout<<"Number of fish expected: "<<max<<endl<<endl;
    }
    return 0;
}