Dies ist ein Übersichtsartikel für DP100 Question Bacha.
(Ich habe überlegt, 100 Fragen zu lösen, aber ich habe es satt, daher denke ich, dass dieser Artikel nicht mehr aktualisiert wird.)
Ich werde versuchen, die DP-Methode so systematisch wie möglich zusammenzufassen.
** DP ist aktiviert, wenn kontinuierliche Einschränkungen bestehen **. Außerdem können wir diesmal sehen, dass es möglich scheint, den Zustand mit 3 Arten von Nudeln zu begrenzen.
Da wir Informationen darüber benötigen, welche Nudeln am ** $ i $ Tag und an wie vielen Tagen hintereinander gegessen wurden **, stellen Sie den DP wie folgt ein (wenn dies kontinuierlich entschieden wird).
$ dp [i] [j] [k]: = $ (Anzahl der Kombinationen von Nudeln $ j $, die von $ i $ day für $ k $ day (1-indiziert) hintereinander gegessen werden)
Der ** Übergang ** sieht folgendermaßen aus: Außerdem betrachten wir hier den Übergang unter der Annahme, dass Sie am ** $ i $ Tag Pasta $ k $ **, ** $ i + 1 $ Tag Pasta $ j $ ** gegessen haben.
(1) Wenn $ k = j $
(2) Wenn $ k! = J $
(✳︎) $ i + 1 $ Wenn die Tagesnudeln festgelegt sind, berücksichtigen Sie nur $ j = Nudeln [i + 1] $, und wenn nicht, berücksichtigen Sie $ j $.
Es können insgesamt ungefähr $ n \ mal 3 \ mal 3 $ mal berechnet werden, und das Maximum beträgt ungefähr $ 1000 $ mal.
mod=10000
n,k=map(int,input().split())
pasta=[-1]*n
for i in range(k):
a,b=map(int,input().split())
pasta[a-1]=b-1
dp=[[[0]*2 for i in range(3)] for j in range(n)]
if pasta[0]==-1:
for i in range(3):
dp[0][i][0]=1
else:
dp[0][pasta[0]][0]=1
#Wo suchst du jetzt?
for i in range(n-1):
if pasta[i+1]!=-1:
#Wo ändert es sich jetzt?(pasta[i]nur)
for j in range(3):
if j==pasta[i+1]:
#Wenn Sie sich selbst wählen
dp[i+1][j][1]+=dp[i][j][0]
#Wenn Sie an einen anderen Ort gehen
for k in range(3):
if k!=j:
dp[i+1][j][0]+=sum(dp[i][k])
else:
for j in range(3):
#Wenn Sie sich selbst wählen
dp[i+1][j][1]+=dp[i][j][0]
#Wenn Sie an einen anderen Ort gehen
for k in range(3):
if k!=j:
dp[i+1][j][0]+=sum(dp[i][k])
ans=0
for i in range(3):
ans+=sum(dp[n-1][i])
print(ans%mod)
Da es rekursiv ist, kann es durch ** rekursives Memo-Making-Verfahren ** gelöst und auf DP reduziert werden.
** Die Zahl erhöht sich immer durch Addition der Ziffernsumme **. Zählen Sie daher die Anzahl der Fälle nach Art der Wiederholung des Memorandums. Das heißt, der DP wird wie folgt eingestellt.
$ dp [i]: = $ (Anzahl der Fälle, in denen es in der Summe der Ziffern zu $ i $ wird)
Wenn die Funktion, die die Summe der Ziffern von $ n $ berechnet, $ check (n) $ ist (der Berechnungsbetrag ist $ O (\ log {n}) $), ist der Übergang wie folgt.
Der Rechenaufwand beträgt $ O (n \ log {n}) $, es reicht also aus.
def check(n):
ret=0
while n!=0:
ret+=(n%10)
n//=10
return ret
n=int(input())
dp=[1]*n
for i in range(n):
c=check(i+1)
if i+c<n:
dp[i+c]+=dp[i]
print(dp[n-1])
** Die Subtraktion von Zahlen kann als Übergang betrachtet werden **. Außerdem ist es schwierig, die Reihenfolge gierig zu bestimmen.
Stellen Sie den folgenden DP ein, da es ausreicht, die Mindestanzahl für jede Nummer zu speichern.
$ dp [i]: = $ (Mindestanzahl von Versuchen, wenn auf $ i $ reduziert)
Darüber hinaus ist der Übergang einfach und wie folgt. Zu diesem Zeitpunkt beträgt die zu reduzierende Zahl $ j = 1 $ ~ $ 3 $.
Hierbei ist zu beachten, dass bestätigt werden muss, dass es sich um $ i-j \ geqq 0 $ (** Referenz außerhalb des Bereichs **) handelt und dass $ i-j $ nicht NG ist.
n=int(input())
ng={int(input()) for i in range(3)}
if n in ng:
print("NO")
exit()
#Die Anzahl der Male
inf=100000000000
dp=[inf]*(n+1)
dp[n]=0
#0,1 falsches Gras
for i in range(n,0,-1):
if dp[i]!=inf:
for j in range(max(i-3,0),i):
if j not in ng:
dp[j]=min(dp[j],dp[i]+1)
print("YES" if dp[0]<=100 else "NO")
4,D - Prediction and Restriction
Es gibt ** und $ 3 ^ n $ Möglichkeiten, ehrlich über die Anzahl der Fälle ** nachzudenken, aber es kann gut zusammengefasst werden, indem ** DP ** verwendet wird, das den Zustand einschränkt. Darüber hinaus kann die Bedingung ** $ K $, die sich vom vorherigen Zug ** unterscheidet, als Übergang angesehen werden.
($ t [i]: = $ ($ i $ Tagesgegnerhand), $ janken [i]: = $ (Punktzahl durch Kauf mit $ i $ Hand))
Sie benötigen Informationen darüber, welche Bewegung für die $ i $ -Zeit ausgeführt werden soll, und der DP kann wie folgt aussehen.
$ dp [i] [j]: = $ (maximale Punktzahl, wenn Sie $ j $ für die $ i $ -Zeit verschieben)
Außerdem ist der Übergang wie folgt (** Ich habe über den Übergang richtig nachgedacht **, also bin ich hier in der Implementierung stecken geblieben). Außerdem ist Goo 0, Choki 1 und Par 0. Beachten Sie auch, dass die ** Initialisierung ** bei $ i = $ 0 ~ $ k-1 $ erfolgt.
Wenn der erste Zug von $ i-k $ $ l $ ist, $ i $ der zweite Zug $ j $ ist, dann ist ** $ l! = J $
(1) Wenn Sie das $ i $ -te Mal gewinnen ... $ (j + 1) % 3 = t [i] $
(2) Wenn Sie für die $ i $ Zeit verlieren oder ziehen
Außerdem ist die maximale Punktzahl, nach der Sie suchen, ** $ mod \ k $ total , sodass die endgültige Antwort $ max (dp [$ nk
n,k=map(int,input().split())
dp=[[0,0,0] for i in range(n)]
janken=list(map(int,input().split()))
t=[0 if i=="r" else 1 if i=="s" else 2 for i in input()]
#Entscheide dich, indem du gleich danach auf die Hand schaust
for i in range(n):
if i<k:
for j in range(3):
if (j+1)%3==t[i]:
dp[i][j]=janken[j]
else:
#aktualisieren
for j in range(3):
#Quelle des Übergangs
for l in range(3):
if j!=l:
if (j+1)%3==t[i]:
dp[i][j]=max(dp[i][j],janken[j]+dp[i-k][l])
else:
dp[i][j]=max(dp[i][j],dp[i-k][l])
ans=0
for i in range(n-k,n):
ans+=max(dp[i])
print(ans)
** Es wäre am besten, wenn Sie in der Reihenfolge vom Vortag denken könnten **, und ** die gierige Methode scheint schwierig zu sein ** (eigentlich ist es nicht so schwierig).
(Im Folgenden ist der Vorgang des Kaufs aller Aktien oder des Verkaufs aller Aktien optimal, aber ich werde es hier nicht beweisen.)
Wenn Sie normalerweise über den maximalen Geldbetrag nachdenken, den Sie am $ i $ -Tag haben, wird es sehr schwierig zu klassifizieren, ob Sie Aktien haben oder nicht. In Anbetracht der Tatsache, dass ** endlich alle Aktien verkauft ** **, kann der folgende DP festgelegt werden.
$ dp [i]: = $ (Maximaler Geldbetrag, den Sie beim Verkauf aller Aktien an $ i $ Tag haben)
Wenn Sie zu diesem Zeitpunkt darauf achten, wann Sie alle Aktien kaufen, können Sie den Übergang wie folgt ausdrücken: ** Kauf aller Aktien am $ j $ Tag **.
dp[i]=max(dp[i],(dp[j]//a[j])*a[i]+dp[j]%a[j])
Außerdem beträgt der Berechnungsbetrag $ O (N ^ 2) $, was ausreicht. Zuerst habe ich versucht, es mit $ O (N) $ zu lösen, aber aus den Einschränkungen geht hervor, dass $ O (N ^ 2) $ ausreicht.
n=int(input())
a=list(map(int,input().split()))
dp=[0]*n
dp[0]=1000
for i in range(1,n):
dp[i]=dp[i-1]
for j in range(i):
dp[i]=max(dp[i],(dp[j]//a[j])*a[i]+dp[j]%a[j])
print(dp[n-1])
Ich würde gerne an eine magische Kombination denken, aber ** es scheint schwierig, gierig zu wählen **. ** Wenn Sie die notwendige magische Kraft für jede körperliche Stärke verwalten ** Es sieht gut aus und Sie denken an DP.
Es ist gut, den folgenden DP einzurichten.
$ dp [i]: = $ (Minimale erforderliche magische Kraft, wenn die verbleibende physische Stärke des Monsters $ i $ beträgt)
Zu diesem Zeitpunkt ist der Übergang einfach, und wenn die Kraft einer bestimmten Magie $ a $ und die Kraft der Magie $ b $ beträgt, ist dies wie folgt.
Außerdem kann ** Magie beliebig oft verwendet werden **, sodass Sie den DP in Richtung $ h \ rightarrow0 $ berechnen können.
h,n=map(int,input().split())
inf=100000000000
dp=[inf]*(h+1)
dp[h]=0
for i in range(n):
a,b=map(int,input().split())
for j in range(h,-1,-1):
dp[max(j-a,0)]=min(dp[max(j-a,0)],dp[j]+b)
print(dp[0])
Die Operation kann durch Multiplizieren von $ A \ _i, A \ _j $ mit -1 ** umschrieben ** werden, so dass sie leicht gelöst werden kann, indem die Fälle mit geraden oder ungeraden negativen Zahlen klassifiziert werden. Ich werde.
Selbst ein solches Problem kann jedoch von DP vorangetrieben werden. Dies liegt daran, dass es sinnlos ist, jede Operation mit $ i $ mehr als einmal auszuführen. Daher ist es nur erforderlich, die Operation einmal auszuführen, und zu diesem Zeitpunkt ** können die Operationen von vorne monoton ausgeführt werden **.
Der folgende DP sollte eingestellt werden. (Obwohl $ i $ und $ i + 1 $ in der Operation in der Problemstellung ausgewählt sind, ist die Operation zum Auswählen von $ i-1 $ und $ i $ die $ i $ -te Operation, um die Implementierung zu vereinfachen. Ich werde.)
$ dp [i] [j]: = $ (Maximale Gesamtzahl der Spalten, wenn die Operation bis zur $ i $ -ten Operation ausgeführt wird und die $ i $ -te Operation ausgeführt wird (oder nicht))
Es wird jedoch angenommen, dass $ j = 1 $ nicht ausgeführt wird und $ j = 1 $ ausgeführt wird.
Außerdem ist der Übergang zu diesem Zeitpunkt wie folgt.
(1) Beim Betrieb am $ i $ th
Es ist zu beachten, dass ** $ i-1 $, unabhängig davon, ob die Operation zu diesem Zeitpunkt ausgeführt wurde oder nicht **, $ a [i-1] $ oder $ -a [i-1] $ ändert. ** Achten Sie auf den Unterschied **.
(2) Wenn am $ i $ th keine Operation ausgeführt wird
n=int(input())
a=list(map(int,input().split()))
dp=[[0,0] for i in range(n)]
dp[0][0]=a[0]
dp[1][0]=dp[0][0]+a[1]
dp[1][1]=dp[0][0]-2*a[0]-a[1]
for i in range(2,n):
dp[i][0]=max(dp[i-1])+a[i]
dp[i][1]=max(dp[i-1][0]-2*a[i-1]-a[i],dp[i-1][1]+2*a[i-1]-a[i])
print(max(dp[n-1]))
Es kann geteilt werden, wenn nur die Nachbarn unterschiedlich sind, und der Teilstring sollte so kurz wie möglich sein, um mehr zu teilen. Selbst wenn der Teilstring mit einer Länge von 3 oder mehr geteilt wird, kann zu diesem Zeitpunkt die Bedingung des Subjekts erfüllt sein, daher sollte es sich um eine ** Zeichenfolge mit einer Länge von 1 oder 2 ** handeln. An dieser Stelle werden wir zunächst eine gierige Methode in Betracht ziehen, mit der die Länge der Teilzeichenfolgen so weit wie möglich einzeln festgelegt wird. Sie können jedoch nicht sicher sein, dass die Implementierung etwas umständlich und gerechtfertigt ist. In diesem Fall kann DP auf klare und legitime Weise für ** AC ** verwendet werden.
Schneiden Sie einen Teilstring aus dem vorherigen Zeichen aus, damit die Länge 1 so groß wie möglich ist. Die Länge beträgt nur 2, wenn das Zeichen der Länge 1 unmittelbar vor und gleich dem nächsten Zeichen ausgeschnitten wird. Die Implementierung kann durchgeführt werden, indem der unmittelbar zuvor ausgeschnittene Teilstring aufgezeichnet wird.
s=input()
ans=1
l=len(s)
now=s[0]
i=1
while i<l:
if now!=s[i]:
now=s[i]
ans+=1
i+=1
else:
if len(now)==2:
now=s[i]
ans+=1
i+=1
else:
if i<l-1:
now=s[i:i+2]
i+=2
ans+=1
else:
break
#print(i)
print(ans)
Sie können die Anzahl der Zustände ** begrenzen **, indem Sie beachten, dass Sie nur 1 oder 2 ausschneiden können. Daher kann der DP wie folgt eingestellt werden.
$ dp [i] [j]: = $ ($ i $ th ist ** die größte Anzahl von Teilungen in einer Zeichenfolge mit der Länge $ j + 1 $)
Der Übergang ist auch wie folgt, wenn man den Übergang zu $ dp [i] $ betrachtet. Hier sei das Zeichen $ i $ $ s [i] $.
(1) Wenn das $ i $ th in einer Unterspalte der Länge 1 enthalten ist
Wenn das $ i-1 $ th in der Unterspalte der Länge 2 enthalten ist, kann es unbedingt ausgewählt werden und $ dp [i] [0] = dp [i-1] [1] + 1 $. .. Wenn $ i-1 $ th in einer Unterspalte der Länge 1 enthalten ist, ist $ s [i-1]! = S [i] $, wenn $ dp [i] [0] = max (dp [i] [ 0], dp [i-1] [0] + 1) $.
(2) Wenn das $ i $ th in einer Unterspalte der Länge 2 enthalten ist
Wenn das $ i-2 $ th in einer Unterspalte der Länge 1 enthalten ist, kann es bedingungslos ausgewählt werden und $ dp [i] [1] = dp [i-2] [0] + 1
s=input()
n=len(s)
dp=[[0,0] for i in range(n)]
dp[0][0]=1
for i in range(1,n):
dp[i][0]=dp[i-1][1]+1
if s[i-1]!=s[i]:
dp[i][0]=max(dp[i][0],dp[i-1][0]+1)
if i>1:
dp[i][1]=dp[i-2][0]+1
if i>2:
if s[i-3:i-1]!=s[i-1:i+1]:
dp[i][1]=max(dp[i][1],dp[i-2][1]+1)
print(max(dp[n-1]))
Erstens gibt es $ _ {16} C_2 $ Kombinationen von Verknüpfungen. Berücksichtigen Sie die maximale Anzahl von Tastendrücken, die für jede dieser Verknüpfungskombinationen erforderlich sind. Zu diesem Zeitpunkt ist es schwierig, gierig zu denken, und die Anordnung der Zeichen in der richtigen Reihenfolge kann als Übergang angesehen werden, sodass Sie an DP denken können.
Es wird angenommen, dass der Verknüpfungsbefehl auf $ L, R $ festgelegt ist. Stellen Sie zu diesem Zeitpunkt DP wie folgt ein.
$ dp [i]: = $ (Mindestanzahl der Entscheidungen, bis zu $ i $ entschieden wird)
Der DP-Übergang zu diesem Zeitpunkt ist wie folgt. Hier betrachtete ich die DP als vom $ k $ th übergeben.
(1) Wenn Sie keine Verknüpfungen verwenden
(2) Bei Verwendung von Verknüpfungen
Wenn die Verknüpfung mit den Zeichen $ k + 1 $ und $ k + 2 $ übereinstimmt ($ s [k + 1: k + 3] == l $ oder $ s [k + 1: k + 3] = = r $),
command=[i+j for i in "ABXY" for j in "ABXY"]
#print(command)
n=int(input())
s=input()
inf=100000000000
ans=inf
for i in range(16):
l=command[i]
for j in range(16):
r=command[j]
dp=[inf]*n
dp[0]=1
if n>1:
if s[0:2]==l or s[0:2]==r:
dp[1]=1
for k in range(n):
if k+1<n:
dp[k+1]=min(dp[k+1],dp[k]+1)
if k+2<n:
if s[k+1:k+3]==l or s[k+1:k+3]==r:
dp[k+2]=min(dp[k+2],dp[k]+1)
#print(dp[n-1])
ans=min(ans,dp[n-1])
print(ans)
Im Gegenteil, ich denke, es ist besser, DP nicht für dieses Problem auszuwählen. Mit anderen Worten, Sie können einen ** Extrempunkt ** nehmen, der eine der folgenden Bedingungen erfüllt:
Darüber hinaus sollten Sie gierig sein, diese Bedingung zu erfüllen, und Sie können dies mit der folgenden Richtlinie tun.
Wenn die zuletzt ausgewählte Bewertung $ x $ ist und die Bewertung des Punktes, den Sie betrachten, $ r \ _i $ ist, sind die Bedingungen für die Auswahl von $ r \ _i $ eine der folgenden.
Wenn einer dieser Punkte zutrifft, kann er in das Diagramm des Motivs aufgenommen werden, und Sie können die Elemente nacheinander gierig auswählen.
Außerdem können ** Bewertungen für links und rechts eingeschlossen werden, da sie immer die Bedingungen des Diagramms erfüllen **. Wenn daher die Anzahl der Punkte in dem Diagramm, das gierig ausgewählt wurde, weniger als 3 beträgt, sollte -1 ausgegeben werden, und wenn es 3 oder mehr sind, sollte die Anzahl der Punkte ausgegeben werden.
n=int(input())
r=list(map(int,input().split()))
if n<3:
print(0)
exit()
ans=[r[0]]
for i in range(1,n-1):
if ans[-1]<r[i] and r[i]>r[i+1]:
ans.append(r[i])
if ans[-1]>r[i] and r[i]<r[i+1]:
ans.append(r[i])
if i==n-2:
ans.append(r[i+1])
if len(ans)<3:
print(0)
else:
print(len(ans))
Recommended Posts