Dynamic Pizza

解法1.動的計画法(Dynamic Programming)を利用する解き方

2次元配列 $dp$ を以下のように定義します。

$dp[i][j]:=i$ 個ピザを食べ、最後に食べたピザが $j$ 種類目のピザであるときの食べた $i$ 個のピザの美味しさの総和の最大値

最終的な答えは $\max_{1\le i \le M} dp[N][i]$ です。

$dp[1][j]=A_j$ です。また、 $dp[i+1][j]=\max_{1\le k \le M,k \neq j}(dp[i][k]+A_j)$ です。

これらを元に $\max_{1\le i \le M} dp[N][i]$ の値が時間計算量 $O(NM^2)$で求めることができます。

( $dp[i+1][j]=\max_{1\le k \le M,k \neq j}(dp[i][k]+A_j)$ の計算を工夫すれば $O(NM)$ で求めることもできます。)

実装

注意:このコードをCpythonで提出した場合TLEで出ます。pypyで提出してください。

解法2.貪欲法（Greedy Algorithm）を利用する解き方

食べられるピザの内、最も美味しさが大きいものを食べ続けるのが最適です。 具体的には、美味しさが最も大きいピザの美味しさを $X$ 、2番目に美味しさが大きいピザの美味しさを $Y$ とした時、答えは $\lceil N/2 \rceil * X + \lfloor N/2 \rfloor * Y$ になります。

($\lceil N/2 \rceil$は $N/2$ 以下の最大の整数を表します。また、 $\lfloor N/2 \rfloor$は $N/2$ 以上の最小の整数を表します。)

これは時間計算量 $O(MlogM)$ や $O(M)$ で求めることができます。

実装