Codeforces Round 857 (Div. 1) - C. Music Festival (1900)

C. Music Festival

일단 모든 앨범을 오름차순으로만 트랙을 남길 수 있다.

$dp[i]=i$보다 큰 트랙을 쓰지 않았을 때 앨범들을 써서 최대 정답이라고 하자.

앨범들을 트랙중 가장 크기가 큰 것을 기준으로 오름차순 정렬하면

$i$ 번째 앨범에서 최대 트랙값이 $m_i$ 일 때 $dp[m_i+1]$ 을 채워주기 때문에 $m_i+1$ 미만의 $dp$ 값들은 채워져있다고 가정할 수 있다.

앨범의 모든 트랙 $j$ 들을 순회한다.

앨범의 길이가 $\vert a_i \vert$ 라면 $j$ 번째 트랙부터 정답에 더해진다면 정답으로 얻을 수 있는 값은 $\vert a_i \vert+1-j$ 이고 각 $j$ 에 대해 $dp[m_i+1]=\text{Max} \sum_{j} dp[cool_{i, j}]+\vert a_i\vert+1-j$ 같이 구해줄 수 있다.