C - 節制

[Q] https://atcoder.jp/contests/abc013/tasks/abc013_3

1. はじめに食べれるだけ食べちゃって、終了日ぎりぎりまで絶食すればいい。
2. どれだけ食べるかは、普通の食事を0 ~ N回全探索する。
3. 普通回数が決まれば、質素回数と食事抜き回数は、O(1)で求まる。
4. 普通以外を全部食事抜きとした場合に、不足する満腹度が出る。質素におきかえれば、質素 + 食事抜きの減少分が増加量。

Q. 例1
4 5
100 4 60 1 4

1.) 普通 0 回
・残りの日数
leftday = 4 - 0 = 4
・今の満腹度
energy = 5 + 4 * 0 = 5
・足りない満腹度
lack = leftday * E - energy = 4 * 4 - 5 = 11
・何日質素にすればいいか。
d = lack / (D + E) + 1 = 11 / 5 + 1 = 3 日

DDDE の4日を過ごせる。
ans = 100 * 0 + 60 * 3 = 180 が候補

2.) 普通 1 回
・残りの日数
leftday = 4 - 1 = 3
・今の満腹度
energy = 5 + 4 * 1 = 9
・足りない満腹度
lack = leftday * E - energy = 3 * 4 - 9 = 3
・何日質素にすればいいか。
d = lack / (D + E) + 1 = 3 / 5 + 1 = 1 日

BDEE の4日を過ごせる。
ans = 100 * 1 + 60 * 1 = 160 が候補

答えは160

実装

int main(){
 cincout();
 
 ll N, H, A, B, C, D, E;
 cin >> N >> H >> A >> B >> C >> D >> E;
 
 ll ans = oo;
 ll dif = D+E; // Dをくったときの増加量
 rep(b, N+1){ // Bの日数
   ll leftday = N-b;
   ll energy = H+B*b;
   ll lack = leftday * E - energy;
   ll d=0; // Dの日数
   if (lack>=0){
     d = lack/dif + 1;
   }
   ll score = A*b + C*d;
   chmin(ans, score);
 }
 cout << ans << endl;
}

https://atcoder.jp/contests/abc013/submissions/27464034