ABC285 E - Work or Rest - かんプリンの学習記録

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

曜日 ${1,\dots ,N}$ からなる一週間の各曜日に「平日」か「休日」のどちらかを割り当てる．このとき，曜日 ${i}$ の生産量は以下のように表される．

曜日 ${i}$ が「休日」である場合は ${0}$
曜日 ${i}$ が「平日」のとき，直前の休日が ${x}$ 日前，直後の休日が ${y}$ 日後である場合は ${A_{\min(x,y)}}$

一週間当たりの生産量の最大値を求めよ．

${1\leq N\leq 5000}$
${1\leq A_i\leq 10^9}$

解説

曜日 ${1}$ の前日は曜日 ${N}$ ，というように前後に繋がっているので「平日」「休日」の割り当てを決めた際にrotateをしても答えは変わりません．

つまり，曜日 ${1}$ は必ず休日としてもよいです．

次に，初日が休日で，その後平日が続くようなブロックに分解してみます．

休日 ${1}$ 日＋平日 ${d-1}$ 日の全 ${d(\geq 1)}$ 日からなるブロックの生産量は公式解説の ${B_{d-1}}$ と等しいです．これを ${v_d}$ とします．

すると，この問題は

品物 ${i}$ の重みを ${i}$
品物 ${i}$ の価値を ${v_i}$
品物の重みの合計の上限を ${N}$

としたときの個数制限なしナップサック問題となります．

よって，この問題を時間計算量 ${O(N^2)}$ で解くことができます．

提出プログラム

https://atcoder.jp/contests/abc285/submissions/38167895 C++
https://atcoder.jp/contests/abc285/submissions/38169128 Python

N = int(input())
A = list(map(int,input().split()))
V = [0] * (N+1)
DP = [0] * (N+1)
for i in range(2,N+1):
    V[i] = V[i-1] + A[i//2-1]
    for j in range(i,N+1):
        DP[j] = max(DP[j], DP[j-i] + V[i])
print(DP[N])

感想

ナップサック問題の少し難しい版の問題でした．