Lösen mit Python [100 frühere Fragen, die Anfänger und Fortgeschrittene lösen sollten] (053 --055 Dynamische Planungsmethode: Andere)

1. Zweck

Lösen Sie 100 frühere Fragen, die Anfänger und Fortgeschrittene lösen sollten in Python. Das Ziel ist es, hellblau zu werden, wenn Sie alles gelöst haben.

Dieser Artikel ist "053 - 055 Dynamische Planung: Andere".

2. Zusammenfassung

Wie Sie unter "Andere" sehen können, unterscheiden sich diese drei Fragen in Bezug auf die Ausrichtung (Präferenz?) Etwas von den vorherigen "dp". Und sind "dp", die nicht wie "dp" sind. Ich fühlte, dass.

3. Hauptgeschichte

053 --055 Dynamische Planung: Andere

053. DPL_1_D - Unterspalte mit der längsten Zunahme

Antworten

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))

Löse mit Dichotomie und DP.

dpIn aufsteigender ReihenfolgeaWir werden die Elemente von hinzufügen. Speziell,

1. Für alle `A``` Elemente A [i] `` `
2. Fügen Sie etwas Größeres als das letzte Element von `` dp zu` `dp hinzu
3. Wenn es nicht groß ist, gibt es mehr als `A [i]` in `dp```, also ersetzen Sie es durch` A [i] `` `
4. Die Antwort ist die Länge des abgeschlossenen `` `dp``` ist.

054. AtCoder-Anfängerwettbewerb 006 D - Trump Insert Sort

Antworten

import bisect

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

dp = [C[0]] #Ursprünglicher Wert

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))

53. Es ist fast dasselbe wie DPL_1_D - Unterspalte mit der längsten Zunahme. Der Unterschied ist der letzte `print (N --len (dp))`. Die Häufigkeit, mit der Sie eine Spielkarte einlegen müssen, entspricht der Anzahl der Spielkarten abzüglich der Länge der am längsten wachsenden Unterspalte.

55. AtCoder Beginner Contest 134 E - Sequence Decomposing

Antworten

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))

Lassen Sie uns die Denkweise von den beiden oben genannten Problemen ändern. In den obigen zwei Problemen waren die Elemente über dem Maximalwert von `` `dp````` append```, Dieses Mal werden wir die Elemente unterhalb des Mindestwerts anhängen.