[BOJ]11054-最長のバイナリ部分数列

8493 ワード
boj DP アルゴリズム#アルゴリズム# テキストリンク

質問リンク


最長の2進数列

問題の説明


バイナリ数列は長さNの数列SSSによる特定数SkS kSkである
S1満たされた数の列を表す.
数列を与えた場合、その数列内で最も長いバイナリ部分数列を求める.

問題を解く


テストケースの数
1 5 2 1 4 3 4 5 2 1
の中で、最も長い2進数の列は
1 2 3 4 5 2 1
はい.
この問題は最長の部分数列LISで2回で素早く解くことができます.
  • 特定数iを基準として、数列をseq[:i+1]とsep[i:]の2つに分ける.
  • 分割した2つのseqに対してそれぞれLISを回す.
    ->ここでseq 2はbytonic条件下のSk
  • 2で得られた2つのリストのLISを加算した後、重複カウントの部分を削除する(A[i]).

    • コード#コード#

    import sys
import copy

input = sys.stdin.readline

N = int(input())
seq = list(map(int, input().split()))
answer = 0

for k in range(N):
    seq1 = copy.deepcopy(seq[:k+1])
    seq2 = copy.deepcopy(seq[k:])
    seq2.reverse()
    dp1 = [1]*(len(seq1)+1)
    dp2 = [1]*(len(seq2)+1)

    #LIS 알고리즘
    for i in range(1, len(seq1)):
        for j in range(0, i):
            if seq1[j] < seq1[i]:
                dp1[i] = max(dp1[i], dp1[j]+1)

    #LIS 알고리즘
    for i in range(1, len(seq2)):
        for j in range(0, i):
            if seq2[j] < seq2[i]:
                dp2[i] = max(dp2[i], dp2[j]+1)
    answer = max(answer, max(dp1)+max(dp2)-1)

print(answer)

    に感銘を与える


    LISを知っていれば、接近して解決しやすい問題だと思います.しかし私はまだLISを完全に理解していないで、コードを暗記するしかなくて、위,,,,私をつかんでLISを勉強して、뉫덛、LISを解いてみます!

    そして金色になりましたははは、、、
    多田:AdedJSとFCMのAWSピンポイントプッシュ通知の一致
    プログラマー-最長のパリントロム-C++