白駿11054号最長のVitonic部分数列

7061 ワード
白駿 コセット DP パイ アルゴリズム#アルゴリズム# テキストリンク

白駿11054号最長のVitonic部分数列


https://www.acmicpc.net/problem/11054

Pythonコード

import sys

N = int(sys.stdin.readline())

numbers = list(map(int, sys.stdin.readline().split()))

dp = [0 for _ in range(N)]
dp_inverse = [0 for _ in range(N)]

for i in range(N):
  for v in range(i):
    if numbers[i] > numbers[v]:
      dp[i] = max(dp[i], dp[v])
  dp[i]+=1
    
for i in range(N):
  for v in range(i):
    if numbers[N-1-i] > numbers[N-1-v]:
      dp_inverse[N-1-i] = max(dp_inverse[N-1-i], dp_inverse[N-1-v])
  dp_inverse[N-1-i]+=1

result = 0

for i in range(N):
  result = max(result, dp[i] + dp_inverse[i])

print(result - 1)

解法


ローカル数列問題ではダイナミックプログラミングに慣れていない.
悩みの解決法をご紹介します
  • の数値リストで、お願いニック数列の最大値となる値を指定し、すべて解き、最後に最大値
    • を抽出します.
  • バイト数列では、最大値が数値リストの繰り返し文を迂回し、最大値部分のコアが変化した場合、結果が変化するかどうかを確認し、
    • で更新します.
    この2つの方法は最初から考えられ実施されたことがある.
    数字表を順番に回して、ある値が出るたびに、規則的に変えるよりも、全部取り替えるというケースもあります.
    それぞれに計算をやり直し、それが実現すれば条件文だけでなく時間の複雑さも増す.
    そこで,上記のコードに示すように実装方法を変更した.
    dpに最大
  • 個の順方向昇順を満たす数字を格納
  • は、逆順昇順を満たす最大数をdp逆中
    • に記憶する.
  • dpとdpをインデックスで逆加算ときの最大値は
    • である.
  • ビットのバイナリ数列では、最大カーネル値はdpとdpの逆オーバーラップカウントであるため、結果は-1
    • である.
    TypeError: Cannot read property 'map' of undefined
    Macツールのインストール