競プロ初中級者100問

AOJ1611 ダルマ落とし

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1611&lang=jp

この問題は動的計画法を用いて解くことができます。

方針

i番目のブロックからj番目のブロックまでのうちで取り除くことができるブロック数の最大値をdp[i][j]として表します。

j-iをdとして、奇数の場合は計算が簡単で、計算量を削減できます。

  • dが偶数の場合
    • dp[i+1][j-1]==d-1の場合（間の区間が全て取り除ける場合）
      • 両端を取り除けるかを判定
    • dp[i+1][j-1]!=d-1の場合（間の区間に取り除けないブロックがある場合）
      • dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j])をkでループ
  • dが奇数の場合
    • 全ブロックを削除することはできないので、最善となる偶数の2パターンを考える
      • dp[i][j] = max(dp[i+1][j], dp[i][j-1])

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def solve():
    ans = []
    while(1):
        N = int(input())
        if N==0:
            break
        W = list(map(int,input().split()))
        dp = [[0]*N for _ in range(N)]
        for d in range(1,N):
            for i in range(N-d):
                j = i+d
                if d%2==1:
                    if dp[i+1][j-1]==d-1:
                        if abs(W[i] - W[j])<=1:
                            dp[i][j] = d+1 
                        else:
                            dp[i][j] = d-1
                    for k in range(i+1,j):
                        new = dp[i][k]+dp[k+1][j]
                        if new > dp[i][j]:
                            dp[i][j] = new
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        ans.append(dp[0][-1])
    for a in ans:
        print(a)
solve()

記事情報

  • 投稿日：2020年6月17日
  • 最終更新日：2020年6月17日