いろはちゃんコンテスト Day1：G - 友達以上恋人以下
問題
解法
dp(i, j, k) := i - 1 日目までで，j 回好意をほのめかし，前回のほのめかしから k 日経過しているときの，i 日目以降に得られる機嫌の合計の最大値
と DP をおく．このとき遷移は，i 日目に好意をほのめかすかどうかの 2 パターンがある．もし k == K となったり j > M となったりしたらその時点で問題文の条件を満たさない．O(365 ^ 3) となるが，時間計算量の面では枝刈りが効くので間に合うが，空間計算量においては，DP テーブル・メモ配列の確保を工夫しないと MLE となってしまう．具体的には，常に j <= i であることを利用するなど．
解答
