AOJ 2642 - 夕食 - ツバサの備忘録

解法

$T$ 日間で、 $x_{0}, x_{1}, x_{2}, \dots x_{i} \dots x_{T-2}, x_{T-1}$ 日目に自炊を行ったと仮定します。
このとき、得られる幸福度は以下のようになります。
$\displaystyle \sum C_{i} - \sum_{k = 0}^{T-1}C_{x_{k}} + \sum_{k = 0}^{T-1}(Q + 2k- (x_{k} - 1))P$
はじめの2つの項が食堂で食べることによって得られる幸福度、最後のΣの部分が自炊によって得られる幸福度になります。
これを式変形するとこうなります。
$\displaystyle \sum C_{i} + \sum_{k = 0}^{T-1}(Q + 2k)P - \sum_{k = 0}^{T-1}(C_{x_{k}} + P(x_{k} - 1))$
これを整えると、以下のようになります。
$\displaystyle \sum C_{i} + (Q + T - 1)TP - \sum_{k = 0}^{T-1}(C_{x_{k}} + P(x_{k} - 1))$
よって、自炊を行った日数 $T$ を決め打ちしたときの幸福度の最大値は、 $\displaystyle \sum_{k = 0}^{T-1}(C_{x_{k}} + P(x_{k} - 1))$ を最小にしたときになります。
この値は、 $X_{i}$ の選び方に依存しますが、 $C_{x_{k}} + P(x_{k} - 1)$ を昇順にソートし、小さい順に選んでいけばよいです。
あとは、自炊を行った日数を全探索し、幸福度の最大値を求めれば答えとなります。

感想

とりあえず条件を立式して考える、できたとしても上手く答えにたどり着くかどうか微妙なところですね…