1. 목적

초중급자가 풀어야 할 과거문정선 100문을 파이썬으로 푸십시오.
모두 풀이 끝날 무렵에 하늘색이 되어 있는 것이 목표입니다.

본 기사는 「053 - 055 동적 계획법:기타」입니다.

2. 총괄

「기타」라고 있는 바와 같이 이 3문문은 지금까지의 dp 와는 조금 지향(기호?)가 달라, dp답지 않다 dp 라고 느꼈습니다.

3. 본편

053 - 055 동적 계획법 : 기타

053. DPL_1_D - 최장 증가 부분 열

답변

import bisect

n = int(input())
A = [int(input()) for _ in range(n)]
dp = [A[0]]

for i in range(1, n):
    if A[i] > dp[-1]:
        dp.append(A[i])
    else:
        ind = bisect.bisect_left(dp, A[i])
        dp[ind] = A[i]

print(len(dp))

이분 탐색과 DP로 해결합니다.
dp 에 오름차순으로 A 요소를 순서대로 추가합니다.
구체적으로는

모든 A 요소 A[i] 소개

dp 의 마지막 요소보다 큰 것은 dp 에 추가

크지 않은 경우 dp 안에 A[i] 이상의 숫자가 존재하므로 A[i]로 바꿉니다

완성 dp 의 길이가 대답
입니다.

054. AtCoder Beginner Contest 006 D - 카드놀이 삽입 정렬

답변

import bisect

N = int(input())
C = [int(input()) for _ in range(N)]

dp = [C[0]] # 初期値

for i in range(1, N):
    if C[i] > dp[-1]:
        dp.append(C[i])
    else:
        ind = bisect.bisect_left(dp, C[i])
        dp[ind] = C[i]

print(N - len(dp))

DPL_1_D - 최장 증가 부분 열 과 거의 같습니다.
차이는 마지막 print(N - len(dp)) .
트럼프를 삽입하는 데 필요한 횟수는 트럼프의 수에서 가장 긴 증가 부분 열의 길이를 뺀 수입니다.

055. AtCoder Beginner Contest 134 E - Sequence Decomposing

답변

import bisect
from collections import deque

N = int(input())
A = [int(input()) for _ in range(N)]

dp = deque()
dp.append(A[0])

for i in range(1, N):
    ind = bisect.bisect_left(dp, A[i])

    if ind == 0:
        dp.appendleft(A[i])
    else:
        dp[ind-1] = A[i]

print(len(dp))

위의 두 가지 문제에서 조금만 생각을 바꿉니다.
상기 2개의 문제에서는, dp 의 최대치 이상의 요소를 append 하고 있었습니다만,
이번에는 최소값 이하의 요소를 appendleft 합니다.