Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 267 D問題 Index × A(Not Continuous ver.)

AtCoder ABC267 ABC D問題 400 pts

問題

提出解答

問題の概要

長さ $N$ の整数列 $A=(A_1, \dots, A_N)$ が与えられる.

$A$ の長さ $M$ の連続とは限らない部分列 $B=(B_1, \dots, B_M)$ における $\displaystyle \sum_{i=1}^M i \times B_i$ の最大値を求めよ.

制約

$1 \leq M \leq N \leq 2000$
$-2 \times 10^5 \leq A_i \leq 2 \times 10^5$

解法

動的計画法で求めることにする. $0 \leq i \leq N, 0 \leq j \leq M$ に対して, ${\rm DP}[i,j ]$ で以下のように定める.

$A_1, \dots, A_i$ まで見て, $B_1, \dots, B_j$ まで決定した場合における $\displaystyle \sum_{k=1}^j k \times B_k$ の最大値とする (なお, そのような選び方が存在しない場合は $-\infty$ とする).

ベースケースは $i=0$ のときで,

${\rm DP}[0,j ]=\begin{cases} 0 & (j=0) \\ -\infty & ({\rm otherwise}) \end{cases}$

である.

更新式について, ${\rm DP}[i,j ]$ を求める際に, $B_j$ が $A_i$ 由来か, それ以外の由来かどうかで場合分けすることにより,

${\rm DP}[i,j ]=\begin{cases} 0 & (j=0) \\ \max ({\rm DP}[i-1,j ], {\rm DP}[i-1, j-1 ]+ j \times B_j) & (j \geq 1) \end{cases}$

となる.

この動的計画法によって, 最終解答は ${\rm DP}[N,M ]$ であり, 時間計算量 $O(NM)$ 時間である.