\(d_c[i]\) を「\(1\) 番目から \(i\) 番目までの花壇まで考え、\(i\) 番目の花壇に \(c=1\) ならば花が植えられており、\(c=0\) ならば花が植えられていないとした場合の美しさの合計の最大値」と定義します。

\(d_{c-1}[i-1]\) から \(d_c[i]\) への遷移を考えます。

まず \(d_1[i]\) は \(i\) 番目に花を植える場合なので、\(i-1\) 番目に花を植えてはいけません。したがって、\(d_1[i]=d_0[i-1]+A_i\) です。

また、\(d_0[i]\) は \(i\) 番目に花を植えない場合なので、\(i-1\) 番目に制限はありません。したがって、\(d_0[i]=\max(d_0[i-1],d_1[i-1])\) です。

以上の DP の遷移に基づいて適切に実装することでこの問題に正答することができます。

実装例(Python3)

n = int(input())
a = list(map(int, input().split()))
d0 = [0] * (n + 1)
d1 = [0] * (n + 1)
for i in range(n):
    d0[i + 1] = max(d0[i], d1[i])
    d1[i + 1] = d0[i] + a[i]
print(max(max(d0), max(d1)))