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 "039-045 Dynamische Planung: Knapsack DP-Variante".

2. Zusammenfassung

Das Problem kann gelöst werden, wenn Sie tatsächlich die Ziel-`` `dp```-Tabelle schreiben können, aber es ist schwierig zu lösen, wenn Sie sich die Tabelle nicht vorstellen können.

3. Hauptgeschichte

039 - 045 Dynamische Planung: Rucksack-DP-Variante

039. JOI 2011 Qualifying 4-1st Grade

Antworten


N = int(input())
num = list(map(int, input().split()))
dp = [[0] * (N-1) for _ in range(21)]

for i in range(21):
    if i == num[0]:
        dp[i][0] = 1

for j in range(1, N-1):
    for i in range(21):
        if dp[i][j-1] <= 0:
            continue
        
        if i - num[j] >= 0:
            dp[i - num[j]][j] += dp[i][j-1]
        if i + num[j] <= 20:
            dp[i + num[j]][j] += dp[i][j-1]

answer = dp[num[-1]][N-2]
print(answer)

Die dp-Tabelle vergleicht die Zeilen-Indizes mit der Summe der berechneten Ergebnisse, die Spalten-Indizes mit den angegebenen ganzzahligen Indizes. Notieren Sie in der Tabelle dp "die Anzahl der Fälle, in denen das Berechnungsergebnis genau i ist, in Spalte j".

Die in Eingabebeispiel 1 erstellte dp-Tabelle lautet wie folgt. Die Antwort lautet dp [8] [9](= 10).


    0  1  2  3  4  5  6  7   8   9
0   0  0  0  0  0  0  1  2   4   8
1   0  0  0  0  1  0  0  0   0   0
2   0  0  0  0  0  1  1  3   6  12
3   0  0  1  1  1  0  0  0   0   0
4   0  0  0  0  0  1  2  4   8   8
5   0  1  0  1  1  0  0  0   0   0
6   0  0  0  0  0  1  3  5  10  12
7   0  0  1  1  0  0  0  0   0   0
8   1  0  0  0  0  2  3  4   8  10
9   0  0  1  1  1  0  0  0   0   0
10  0  0  0  0  0  2  4  6  12  12
11  0  1  0  1  1  0  0  0   0   0
12  0  0  0  0  0  2  2  4   8  10
13  0  0  1  1  1  0  0  0   0   0
14  0  0  0  0  0  0  3  6  12  10
15  0  0  0  0  1  0  0  0   0   0
16  0  0  0  0  0  1  1  3   6   8
17  0  0  0  1  1  0  0  0   0   0
18  0  0  0  0  0  1  2  3   6  12
19  0  0  0  0  1  0  0  0   0   0
20  0  0  0  0  0  1  1  1   2   8

Ich denke, es ist eine gute Idee, zuerst diese Tabelle zu schreiben und dann den Code zu schreiben, der diese Tabelle realisiert. Wenn ich mich daran gewöhne, stelle ich mir vielleicht vor, dass ich Code direkt schreiben kann, ohne diese Tabelle zu schreiben, aber ich kann ihn nicht lösen, ohne noch eine Tabelle zu schreiben.

040. JOI 2012 Qualifying 4-Pasta

Antworten


N, K = map(int, input().split()) #K Tage von N Tagen wurden bereits entschieden
pastas = [0] * (N+1)
for _ in range(K):
    A, B = map(int, input().split())
    pastas[A] = B
dp = [[0] * (N+1) for _ in range(4)]
MOD = 10**4

dp[1][0] = 1

for j in range(1, N+1):
    if pastas[j] == 0:
        for i in range(1, 4):
            for k in range(1, 4):
                dp[i][j] += dp[k][j-1]
        for i in range(1, 4):
            if j -2 > 0 and dp[i][j-1] > 0 and dp[i][j-2] > 0:
                dp[i][j-1] -= dp[i][j-2] #Subtrahieren Sie die vor 2 Tagen, damit sie 3 Tage oder länger nicht fortgesetzt wird
                dp[i][j] -= dp[i][j-2] #Subtrahieren Sie die vor 2 Tagen, damit sie 3 Tage oder länger nicht fortgesetzt wird
    else:
        for k in range(1, 4):
            dp[pastas[j]][j] += dp[k][j-1]
        if j - 2 > 0 and dp[pastas[j]][j-1] > 0 and dp[pastas[j]][j-2] > 0:
            dp[pastas[j]][j-1] -= dp[pastas[j]][j-2] #Subtrahieren Sie die vor 2 Tagen, damit sie 3 Tage oder länger nicht fortgesetzt wird
            dp[pastas[j]][j] -= dp[pastas[j]][j-2] #Subtrahieren Sie die vor 2 Tagen, damit sie 3 Tage oder länger nicht fortgesetzt wird

answer = 0
for i in range(1, 4):
    answer += dp[i][-1]
print(answer % MOD)

Es gibt das Gefühl, dass es gewaltsam gelöst wurde, aber es ist AC oben. In vielen Antwortbeispielen wird die `dp``` -Tabelle in 3D erstellt, aber es war schwierig, ein Bild in 3D zu erhalten, und es wurde in 2D gelöst. Das Ziel der zu erstellenden `dp``` -Tabelle besteht darin, eine Tabelle wie die folgende zu erstellen, wobei der Zeilenindex als Pastatyp, der Spaltenindex als Anzahl der Tage und der Inhalt der Tabelle als Anzahl der Fälle verwendet werden. Bei Eingabebeispiel 2)


   0  1  2  3   4   5   6    7    8     9    10    11    12    13    14    15     16     17      18      19       20
0  0  0  0  0   0   0   0    0    0     0     0     0     0     0     0     0      0      0       0       0        0
1  1  1  2  8   0  22  38  104  306  1120     0  1120  3360     0  3360  6720  16800  50400  134400  366240  1370880
2  0  1  2  8   0  22  38  104  410     0  1120  1120     0  3360     0  6720  20160  47040  134400  369600  1370880
3  0  1  2  6  16   0  44  120  404     0     0  1120     0     0  3360  6720  16800  50400  134400  366240  1370880

Der Vorgang zum Erstellen dieser Tabelle ist wie folgt. Da es lang ist, können Sie es auf `` `j = 5``` setzen.



j=1----------
Bei normaler Zugabe ↓
   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
Nach dem Löschen aufeinanderfolgender Dinge ↓
   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
j=2----------
Bei normaler Zugabe ↓
   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  3  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  3  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  3  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
Nach dem Löschen aufeinanderfolgender Dinge ↓
   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  3  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  3  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  3  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
j=3----------
Bei normaler Zugabe ↓
   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  3  9  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  3  9  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  3  9  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
Nach dem Löschen aufeinanderfolgender Dinge ↓
   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  2  8  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  2  8  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  2  8  0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
j=4----------
Bei normaler Zugabe ↓
   0  1  2  3   4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0   0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  2  8   0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  2  8   0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  2  8  24  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
Nach dem Löschen aufeinanderfolgender Dinge ↓
   0  1  2  3   4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0   0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  2  8   0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  2  8   0  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  2  6  22  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
j=5----------
Bei normaler Zugabe ↓
   0  1  2  3   4   5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0   0   0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  2  8   0  22  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  2  8   0  22  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  2  6  22  22  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
Nach dem Löschen aufeinanderfolgender Dinge ↓
   0  1  2  3   4   5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20
0  0  0  0  0   0   0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
1  1  1  2  8   0  22  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2  0  1  2  8   0  22  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
3  0  1  2  6  16  16  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0

dpWenn Sie eine Tabelle erstellen können, ist die Summe in der letzten Spalte die Antwort.

041. JOI 2013 Qualifying 4-Hot Days

Antworten


D, N = map(int, input().split()) #D Tag, N Arten von Kleidung
T = [0] + [int(input()) for _ in range(D)] #Temperatur eines jeden Tages
clothes = [tuple(map(int, input().split())) for _ in range(N)] #(Untere Grenztemperatur, obere Grenztemperatur, Auffälligkeit)
dp = [[0] * (D+1) for _ in range(N)]

for j in range(2, D+1):
    for i in range(N):
        if T[j] < clothes[i][0] or clothes[i][1] < T[j]:
            continue
        score = 0
        for k in range(N):
            if T[j-1] < clothes[k][0] or clothes[k][1] < T[j-1]:
                continue
            score = max(score,
                        abs(clothes[i][2] - clothes[k][2]) + dp[k][j-1])
        dp[i][j] = score

answer = 0
for i in range(N):
    answer = max(answer, dp[i][-1])

print(answer)

Das Ziel dieser `` `dp``` -Tabelle ist es, eine Tabelle wie die folgende zu erstellen, mit dem Zeilenindex als Kleidung, dem Spaltenindex als Datum und dem Inhalt als absolutem Wert für die Auffälligkeit. (Bei Eingabebeispiel 1)


   0  1   2   3
0  0  0   0   0
1  0  0  50   0
2  0  0  20  80
3  0  0   0   0

Wenn Sie diese Tabelle erstellen können, ist die Antwort der Maximalwert in der letzten Spalte.

042. JOI 2015 Qualifying 4-Silk Road

Antworten


INF = float('inf')
N, M = map(int, input().split()) # N+1 Stadt, muss innerhalb von M Tagen tragen
D = [0] + [int(input()) for _ in range(N)] #Stadtentfernung
C = [0] + [int(input()) for _ in range(M)] #Schlechtes Wetter. Müdigkeit ist C.*D aber 0, wenn nicht bewegt
MAX_break = M - N

# dp[i][j] :=Minimale Müdigkeit, um i am Tag j zu erreichen

dp = [[INF] * (M+1) for _ in range(N+1)]

for j in range(M+1):
    dp[0][j] = 0

for i in range(1, N+1):
    for j in range(1, M+1):
        dp[i][j] = min(dp[i][j-1],
                       dp[i-1][j-1] + D[i] * C[j])

print(dp[-1][-1])

Das Ziel dieser `` `dp``` -Tabelle ist es, eine Tabelle wie die folgende zu erstellen, wobei die Zeilen-Indizes verschoben werden, die Spalten-Indizes als Datumsangaben und der Inhalt als Mindestabstand. (Bei Eingabebeispiel 1)


     0      1       2       3       4       5
0  0.0    0.0     0.0     0.0     0.0     0.0
1  inf  500.0   300.0   150.0   150.0   150.0
2  inf    inf  1250.0   675.0   675.0   675.0
3  inf    inf     inf  1475.0  1275.0  1125.0

Wenn diese Tabelle erstellt werden kann, lautet die Antwort `dp [-1] [-1]`.

043. Pakencamp 2019 D - Flagge der Takcamp-Armee

Antworten


import numpy as np

INF = float('inf')
N = int(input())
S = [[''] + list(input()) for _ in range(5)]
S_count = np.zeros((4, N+1))
for j in range(1, N+1):
    for i in range(5):
        if S[i][j] == 'R':
            S_count[0, j] += 1
        if S[i][j] == 'B':
            S_count[1, j] += 1
        if S[i][j] == 'W':
            S_count[2, j] += 1
        if S[i][j] == '#':
            S_count[3, j] += 1

S_to_use = np.zeros((3, N+1))
for j in range(1, N+1):
    for i in range(3):
        S_to_use[i, j] = S_count[:, j].sum() - S_count[i, j]

dp = np.full((3, N+1), INF)
dp[:, 0] = 0
# dp[i, j] :=Minimaler Wert beim Malen der j-ten Spalte auf i

for j in range(1, N+1):
    for i in range(3):
        for k in range(3):
            if i == k:
                continue
            dp[i, j] = min(dp[i, j],
                           dp[k, j-1] + S_to_use[i, j])

answer = dp[:, -1].min()
print(int(answer))

In dieser `` `dp``` -Tabelle ist der Zeilenindex die Flag-Farbe (R: 0, B: 1, W: 2), der Spaltenindex ist die Spaltennummer und der Inhalt sind die kleinsten gemalten Zellen. Als Zahl besteht das Ziel darin, eine Tabelle wie die folgende zu erstellen. (Im Fall von Eingabebeispiel 4)


     0    1    2     3     4     5     6     7
0  0.0  4.0  6.0  12.0  13.0  15.0  18.0  23.0
1  0.0  3.0  8.0  11.0  11.0  17.0  19.0  21.0
2  0.0  4.0  7.0   8.0  15.0  15.0  20.0  21.0

Die Antwort ist der Mindestwert in der rechten Spalte dieser Tabelle.

In dieser Ausgabe mussten wir eine Vorverarbeitung entwickeln, bevor wir die `dp``` -Tabelle erstellen konnten. Insbesondere S_to_use`` im Antwortcode, was zum Beispiel``S_to_use [0, 2]`` bedeutet, was notwendig ist, um die zweite Spalte des Flags auf R zu malen. Repräsentiert die Anzahl der Quadrate. Wenn ich das schaffen könnte, dachte ich, es wäre nicht so schwierig, eine ``dp``` Tabelle zu erstellen.

044. AOJ 1167 - Pollock Forecast

Antwort (TLE)



def cal(i):
    return i * (i + 1) * (i + 2) // 6

def main(n):
    proku = [0]
    proku_odd = [0]
    for i in range(1, 201):
        num = cal(i)
        proku.append(num)
        if num % 2 != 0:
            proku_odd.append(num)

    dp = [0] * (n+1)
    dp_odd = [0] * (n+1)

    for j in range(n+1):
        dp[j] = j
        dp_odd[j] = j

    for i in range(1, len(proku)):
        for j in range(1, n+1):
            if j-proku[i] < 0:
                continue
            if dp[j] > dp[j-proku[i]] + 1:
                dp[j] = dp[j-proku[i]] + 1

    for i in range(1, len(proku_odd)):
        for j in range(1, n+1):
            if j-proku_odd[i] < 0:
                continue
            if dp_odd[j] > dp_odd[j-proku_odd[i]] + 1:
                dp_odd[j] = dp_odd[j-proku_odd[i]] + 1

    print(dp[-1], dp_odd[-1])


if __name__ == "__main__":
    while True:
        n = int(input())
        if n == 0:
            break
            
        main(n)

tleIch habe es nicht behoben, aber ich denke, es ist wahrscheinlich das. Es ist ein wenig schwer, die Problemstellung zu verstehen, aber es ist nicht so schwer zu tun, es ist nur ein normales `` dp```.

Es kann auf die gleiche Weise gelöst werden wie das Rucksackproblem (Problem 36), das Duplikate zulässt.

045. AOJ 2199 - Differenzpulscodemodulation

Antwort (TLE)


def main(N, M, C, X):
    dp = [[INF] * 256 for _ in range(N+1)]
    dp[0][128] = 0

    for i in range(1, N+1):
        for j in range(256):

            for k in range(M):
                next_j = j + C[k]
                next_j = max(0, min(255, next_j))

                dp[i][next_j] = min(dp[i][next_j],
                                    dp[i-1][j] + pow(next_j - X[i-1], 2))

    answer = min(dp[N][:])
    
    return answer


if __name__ == "__main__":
    INF = float('inf')
    answer_list = []
    while True:
        
        N, M = map(int, input().split()) #N ist die Anzahl der Eingänge, M ist die Anzahl der Zahlen im Codebuch
        if N == M == 0:
            break

        C = [int(input()) for _ in range(M)] #Codebuch
        X = [int(input()) for _ in range(N)] #Eingegebener Wert

        answer_list.append(main(N, M, C, X))

    for answer in answer_list:
        print(answer)

Das Problem ist schwer zu lesen. Wieder wäre der obige Code "TLE". Ich denke, das ist richtig, weil alle Antworten lokal gleich sind. Es war ein wenig schwierig zu beschleunigen, also werde ich es tun, wenn ich Lust dazu habe.

Lösen Sie mit Python [100 frühere Fragen, die Anfänger und Fortgeschrittene lösen sollten] (039 - 045 Dynamische Planungsmethode: Knapsack DP-Variante)

1. Zweck

2. Zusammenfassung

3. Hauptgeschichte

039 - 045 Dynamische Planung: Rucksack-DP-Variante

039. JOI 2011 Qualifying 4-1st Grade

Antworten

040. JOI 2012 Qualifying 4-Pasta

Antworten

041. JOI 2013 Qualifying 4-Hot Days

Antworten

042. JOI 2015 Qualifying 4-Silk Road

Antworten

043. Pakencamp 2019 D - Flagge der Takcamp-Armee

Antworten

044. AOJ 1167 - Pollock Forecast

Antwort (TLE)

045. AOJ 2199 - Differenzpulscodemodulation

Antwort (TLE)