【今日の精進】ABC209F - Deforestation

毎日格上の問題を倒すやつの42日目です。

問題リンク

atcoder.jp

問題概要

本の木があるよ。

ある木を伐採するコストは、その木と両端の木の高さの合計だよ。

コストの最小値を達成する伐採方法の数を で割った余りを求めてね。

解法

となりあわせになっている木について、高い方から先に伐採する必要があります。ただし同じ高さの時はどっちでも。

いわゆる挿入DPです。最後に見た木を何番目に伐採したかを情報に持つことで、いい感じにDPができます。

累積和で高速化する必要があることに注意。*1

提出コード

MOD=10**9+7
N=int(input())
H=list(map(int,input().split()))
dp=[[0 for i in range(N+1)] for i in range(N)]
dp[0][0]=1
for i in range(N-1):
    if H[i]==H[i+1]:
        add=sum(dp[i])
        for j in range(i+2):
            dp[i+1][j]=add
    elif H[i]>H[i+1]:
        for j in range(N-1):
            dp[i][j+1]+=dp[i][j]
        for j in range(i+2):
            dp[i+1][j]=dp[i][j-1]
    else:
        for j in range(N):
            dp[i][-j-2]+=dp[i][-j-1]
        for j in range(i+2):
            dp[i+1][j]=dp[i][j]
    for j in range(N):
        dp[i+1][j]%=MOD
print(sum(dp[-1])%MOD)

Submission #47123204 - AtCoder Beginner Contest 209

感想

挿入DPの練習問題的な位置付けなのかな

*1:雑