バックアップ:最大数削減(11722)

4025 ワード
白駿 DP テキストリンク

Dynamic Programming


質問する


数列Aが与えられると、最長の減少部分数列を求めるプログラムが作成される.
例えば、A={10,30,10,20,20,10}を数えると、最も減衰が長い部分はA={10,30,10,20,20,10}となり、長さは3となる.

入力


第1行は、数列AのサイズN(1≦N≦1000)を与える.
2行目は、数列Aを構成するAiを与える.(1 ≤ Ai ≤ 1,000)

しゅつりょく


第1行出力数列Aの最長減少部分数列の長さ.
n = int(input())
a = list(map(int, input().split()))
dp = [1 for i in range(n)]

for i in range(1, n):
    s = []
    for j in range(i): # i 이전까지의 값들과 대소 비교
        if a[j] < a[i]:
            s.append(dp[j]) # 감소관계가 확인되면 j까지의 부분감소수열 값을 더한다.
    if not s:
        continue
    else:
        dp[i] += max(s) # 여러 부분감소수열 중에 가장 큰 값 누적
        
print(max(dp))
注)https://pacific-ocean.tistory.com/209
I/O-スキャンおよび上書き文字
one-hot符号化方式のpython実現