第1部基礎アルゴリズム(向上編)--第1章貪欲アルゴリズム1431:釣り

1431:釣り
時間制限:1000 msメモリ制限:65536 KB提出数:936通過数:444【タイトル説明】水平道端にn個の釣り湖があり、左から右へ1,2,...,n.佳佳はH時間の暇があって、彼はこの時間を利用してもっと多くの魚を釣ることを望んでいます.彼は1から出発して、右に歩いて、いくつかの湖のそばに一定の時間(5分の倍数)釣りを滞在することを選択しました.最後にある湖で釣りを終えた.佳佳はi番目の湖からi+1番目の湖まで歩く必要があります5×Ti分路は、i番目の湖に滞在することも測定され、最初の5分でFi匹の魚を釣ることができ、その後5分ごとに釣ることができる魚の量はDiを減らし、減少後の魚の量が0未満であれば減少後の魚の量は0となる.問題を簡略化するために、佳佳は他の人が釣りをしていないと仮定し、他の要素も彼が所望の数の魚を釣ったことに影響を与えていない.プログラミングして佳佳が最も釣りができる数を求めてください.
【入力】1行目の整数nは、湖の個数を表す
2行目の整数Hは、佳佳の空き時間を表す
3行目にはn個の整数があり、湖ごとに最初の5分で魚が釣れる数を順番に表しています.
4行目にはn個の整数があり、以降の5分ごとの釣り数が前の5分より減少した数を順次示す
5行目にはn−1個の整数があり,Tiはi番目の湖からi+1番目の湖には花が必要であることを示した.×Ti分の道のり
【出力】出力は1行のみで、佳佳が最も釣りができる数を示す.
【入力サンプル】3 1 4 5 6 1 2 1 2【出力サンプル】35【ヒント】サンプル解釈:
1番目の湖で15分釣って、全部で4+3+2=9匹の魚を釣った.
2番目の湖で10分間釣り、5+3=8匹の魚を釣った.
3番目の湖で20分釣って、全部で6+5+4+3=18匹の魚を釣った.
1番目の湖から2番目の湖、2番目の湖から3番目の湖まで、共用時間15分で35匹の魚が得られ、これが最も多い数です.
構想:第一歩:まずすべての時間を5分に変換して計算し、1時間に12個の5分があれば、釣りを1回使用する最初の5分は直接1を減らす.ステップ2:1、i番目の池で計算します.2、i番目の池までは、まず道のりでかかる5分を差し引いてから釣りを行い、各池の現在の釣りの個数を優先キューで格納し、j番目の池釣りを選択した後、j番目の池の釣りの数を更新すると、優先的にキューに押し込まれます.ステップ3:時間が0になるまでステップ2を継続して実行するか、優先キュー内のすべての釣り量<=0の場合にジャンプし、答えを更新してステップ1に戻る.

 #include
 #include
 #include
 #include
 #include
 using namespace std;
 const int N = 110;
 int dis[N],n,h;
struct Node {
     int Fish , Dec ;
     bool operator < ( const Node & rhs ) const {
         return Fish < rhs.Fish ;
     }
 }a[N];
 

 int main()
 {
     scanf("%d%d",&n,&h);
     for (int i=1;i<=n;i++) scanf("%d",&a[i].Fish);
     for (int i=1;i<=n;i++) scanf("%d",&a[i].Dec);
     for (int i=2;i<=n;i++) scanf("%d",&dis[i]);
 
     h *= 12 ;
 
     int sum = 0 , ans = 0 ;
     for ( int i = 1 ; i <= n ; i++ ){
         h -= dis[i] ;
         sum = 0 ;
         priority_queue < Node > q ;
         for ( int j = 1 ; j <= i ; j++ ){
             q.push ( a[j] ) ;
         }
         int time = h ;
         while ( time > 0 ){
             Node cur = q.top() ;
             q.pop() ;
 
             if( cur.Fish <= 0 )
                 break ;
 
             sum += cur.Fish ;
             time -- ;
 
             cur.Fish -= cur.Dec;
             q.push(cur);
         }
         ans = max ( ans , sum ) ;
    }
     printf("%d
",ans);
     return 0;
 }