AOJ 2642 Dinner - 足跡-sokuseki-

Dinner | Aizu Online Judge
AOJ-ICPC 550点…？

問題概要

$N$ 日間の夕食を食堂か自炊のどちらかで済ませる。
$i$ 日目に食堂で夕食をとると幸福度が $C_i$ 得られる。
各日に自炊をすると得られる幸福度は、 (自炊をした時点での自炊パワー) $\times P$ である。
自炊パワーは、初期値が $Q$ であり、食堂に行くたびに 1 減り、自炊をするたびに 1 増える（食事の終了時に変動する）。
$N$ 日間の幸福度の総和の最大値を求めよ。

制約

$1 \le N \le 500,000$
$0 \le P \le 500,000$
$|Q| , |C_i| \le 500,000$

解法

気づくべき重要な点は、ある日に自炊によって得られる幸福度は、「その日以前に何日自炊し、何日食堂に行ったか」のみに依存するということである。
自炊を $x$ 日行い、食堂に $y$ 日行ったとき、 $x+y+1$ 日目に自炊をすると幸福度は $(Q+x-y)P$ 得られる。

ここで、 $N$ 日間で $K$ 日自炊したときの幸福度を式にしてみる。
$sum := C_0 + C_1 + … + C_{N-1}$ とし、
自炊した日を $a_0$ 日目, $a_1$ 日目, … , $a_{K-1}$ 日目（0-indexed）とする。

$a_i$ 日目以前に自炊した日数が $i$ 日で食堂に行った日数が $a_i - i$ 日なので、 $a_i$ 日目の自炊パワーは、 $Q+i-(a_i-i) = Q - a_i + 2i$ となる。
よって、 $a_i$ 日目に自炊したときの幸福度は $(Q - a_i + 2i)P$ であり、 $K$ 日の自炊で得られる幸福度は $\displaystyle \sum _{i=0}^{K-1} (Q-a_i+2i)P$ である。
一方、食堂で得られる幸福度の総和は $sum - \displaystyle \sum_{i = 0}^{K-1} C_{a_i}$ である。

以上から、自炊した日を $a_0$ 日目, $a_1$ 日目, … , $a_{K-1}$ 日目としたときの幸福度の総和は
$sum - \displaystyle \sum_{i = 0}^{K-1} C_{a_i} + \sum _{i=0}^{K-1} (Q-a_i+2i)P$
となる。
これを変形すると、
$sum - \displaystyle \sum_{i = 0}^{K-1} C_{a_i} + \sum _{i=0}^{K-1} (Q - a_i + 2i)P$
$= sum + \displaystyle \sum _{i=0}^{K-1} \{(Q - a_i + 2i)P-C_{a_i} \}$
$= sum + \displaystyle \sum _{i=0}^{K-1} (QP - a_iP + 2iP-C_{a_i} )$
$= sum + KQP + 2 \frac{K(K-1)}{2} P - \displaystyle \sum _{i=0}^{K-1} ( a_iP + C_{a_i} )$
$= sum + KQP + K(K-1) P - \displaystyle \sum _{i=0}^{K-1} ( a_iP + C_{a_i} )$
となり、これを最大化したいので、 $a_0, a_1, … , a_{K-1}$ は $iP + C_i$ が小さいものから $K$ 個選んでくるのが最適となる。

よって、 $K$ を全探索してあげると良い。