Résolution avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (053 --055 Méthode de planification dynamique: Autres)

1. Objet

Résolvez 100 questions passées que les débutants et les intermédiaires devraient résoudre en Python. L'objectif est de devenir bleu clair lorsque vous avez terminé de tout résoudre.

Cet article s'intitule "053 --055 Planification dynamique: autres".

2. Résumé

Comme vous pouvez le voir dans "Autre", ces trois questions sont un peu différentes du précédent dp``` en termes d'orientation (préférence?), Et sont dp qui ne sont pas comme `` dp. J'ai ressenti cela.

3. Histoire principale

053 --055 Planification dynamique: Autre

053. DPL_1_D - Sous-colonne d'augmentation la plus longue

Répondre

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

Résolvez avec dichotomie et DP.

dpDans l'ordre croissantaNous ajouterons les éléments de. En particulier,

1. Pour tous les éléments A ```A [i] `` `
2. Ajoutez quelque chose de plus grand que le dernier élément de `` dp``` à `dp```
3. S'il n'est pas grand, il y a un nombre supérieur ou égal à A [i] in`` dp```, alors remplacez-le par ```A [i] ``.
4. La réponse est la longueur du `` dp '' complété est.

054. AtCoder Beginner Contest 006 D --Trump Insert Sort

Répondre

import bisect

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

dp = [C[0]] #valeur initiale

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. C'est presque la même chose que DPL_1_D - Sous-colonne d'augmentation maximale. La différence est le dernier print (N --len (dp)) ''. Le nombre de fois où vous devez insérer une carte à jouer est le nombre de cartes à jouer moins la longueur de la sous-colonne croissante la plus longue.

55. AtCoder Beginner Contest 134 E - Sequence Decomposing

Répondre

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

Changeons la façon de penser des deux problèmes ci-dessus. Dans les deux problèmes ci-dessus, les éléments au-dessus de la valeur maximale de `` dp``` étaient `ʻappend, Cette fois, les éléments en dessous de la valeur minimale sont appendleft```.