ABC016C 節制 つるかめ算

問題

現在の満腹度はHです。
N日間の間，普通の食事をするとA円出費し満腹度がB増えます。
質素な食事をするとC円出費し満腹度がD増えます。
食事をしないと満腹度がE減ります。
満腹度を０以下にせずN日過ごす場合の最低の出費額を求めます。

C - 節制

考察

最初に食べだめをしておくことは思いつきやすいところです。
普通の食事をする回数と質素な食事をする回数を全探索すると計算量はO(N^2)でN<=10^5だとTLEしますが，N<=1000なら間に合います。

部分点コード

#include <bits/stdc++.h>
using namespace std;

int main(){
  long long N,H,A,B,C,D,E,minM;
  minM=1000000000000;
  cin>>N>>H>>A>>B>>C>>D>>E;
  //cout<<N<<" "<<H<<endl;
  for(int i=0;i<=N;i++){
    for(int j=0;j<=N-i;j++){
      //cout<<i<<" "<<j<<" "<<i*A+j*C<<endl;
      if((H+B*i+D*j-(N-i-j)*E)<=0) continue;
      minM=min(minM,i*A+j*C);  
    }
  }
  cout<<setprecision(18)<<minM<<endl;
  return 0;
}

つるかめ算

更に考察すると，最初に普通の食事だけでのりきる場合の普通の食事の最低限度を計算し，普通の食事をとる日数を１日づつ減らして，必要な日数分質素な食事をとる，というようにすると計算量　O(N)で解けそうです。最初全部どちらかにしてしまう，というのは，つるかめ算の考え方ですね。つるかめ算同様に最後のところも探索せずに割り算でだせばO(1)で解けそうですがバグらせそうなので今日はここまで。

なお，１日も食事しなくても乗り切れる場合も考えられるのでその場合は0を出力します。

ACしたコード

#include <bits/stdc++.h>
using namespace std;

int main(){
  long long N,H,A,B,C,D,E;
  cin>>N>>H>>A>>B>>C>>D>>E; 
  //一度も食事をしない場合を考える
  long long needs=N*E-H+1;
  //一度も食事をしなくても大丈夫なら0を出力
  if(needs<=0){
    cout<<0<<endl;
    return 0;
  }
  //全部高価な食事をする場合のcost
  long long taka = (needs-1)/(B+E)+1;
  long long cost=taka*A;
  long long yasu=0;
  
  //cout<<taka<<" "<<cost<<endl;
  //安価な食事におきかえて足りるかを検討　より安価ならcost更新
  while(taka>0){
    taka--;
    yasu=(needs-taka*(B+E)-1)/(D+E)+1;
    if(yasu + taka <= N){
      cost=min(cost,taka*A+yasu*C);
    }
  }
  cout<<cost<<endl;
  return 0;
}