Ceci est un article de révision pour DP100 Question Bacha.
(Je pensais résoudre 100 questions, mais j'en ai marre, donc je pense que cet article arrêtera de se mettre à jour.)
Je vais essayer de résumer la méthode DP le plus systématiquement possible.
** DP est activé s'il y a des contraintes continues **. De plus, cette fois, nous pouvons voir qu'il semble possible de ** limiter l'état avec 3 types de pâtes **.
Puisque nous avons besoin d'informations sur les pâtes consommées le ** $ i $ jour et le nombre de jours consécutifs **, définissez le DP comme suit (si cela est décidé en continu).
$ dp [i] [j] [k]: = $ (le nombre de combinaisons qui mangent des pâtes $ j $ par $ i $ jour pour $ k $ jour (index 1) d'affilée)
La ** transition ** ressemble à ceci: Nous considérons également ici la transition en supposant que vous avez mangé des pâtes $ k $ **, ** $ i + 1 $ jour pâtes $ j $ ** le ** $ i $ jour.
(1) Lorsque $ k = j $
(2) Lorsque $ k! = J $
(✳︎) $ i + 1 $ Si le jour des pâtes est décidé, considérez seulement $ j = pasta [i + 1] $, sinon, considérez tout $ j $.
Un total d'environ $ n \ fois 3 \ fois 3 $ fois peut être calculé, et le maximum est d'environ 1000 $ fois.
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
#Où cherchez-vous maintenant
for i in range(n-1):
if pasta[i+1]!=-1:
#Où est-ce que ça change maintenant(pasta[i]seulement)
for j in range(3):
if j==pasta[i+1]:
#Si tu te choisis
dp[i+1][j][1]+=dp[i][j][0]
#En allant dans un endroit différent
for k in range(3):
if k!=j:
dp[i+1][j][0]+=sum(dp[i][k])
else:
for j in range(3):
#Si tu te choisis
dp[i+1][j][1]+=dp[i][j][0]
#En allant dans un endroit différent
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)
Comme il est récursif, il peut être résolu par la ** procédure récursive de création de mémos ** et peut être réduit à DP.
** Le nombre augmentera toujours en ajoutant la somme des chiffres **. Par conséquent, comptez le nombre de cas à la manière de la récurrence du mémorandum. Autrement dit, le DP est réglé comme suit.
$ dp [i]: = $ (nombre de cas où il devient $ i $ dans l'opération de somme de chiffres)
Si la fonction qui calcule la somme des chiffres de $ n $ est $ check (n) $ (le montant du calcul est $ O (\ log {n}) $), la transition sera la suivante.
Le montant du calcul est $ O (n \ log {n}) $, donc ce sera suffisant.
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])
** La soustraction de nombres peut être considérée comme une transition **. De plus, ** il est difficile de décider avidement de l'ordre **.
Puisqu'il suffit d'enregistrer le nombre minimum de fois pour chaque nombre, définissez le DP suivant.
$ dp [i]: = $ (nombre minimum de tentatives lorsqu'il est réduit à $ i $)
De plus, la transition est facile et se déroule comme suit. À ce stade, le nombre à réduire est $ j = 1 $ ~ 3 $ $.
Il faut noter ici qu'il est nécessaire de confirmer qu'il s'agit de $ i-j \ geqq 0 $ (** référence hors limites **) et que $ i-j $ n'est pas NG.
n=int(input())
ng={int(input()) for i in range(3)}
if n in ng:
print("NO")
exit()
#Le nombre de fois
inf=100000000000
dp=[inf]*(n+1)
dp[n]=0
#0,1 herbe erronée
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
Il existe ** et $ 3 ^ n $ façons de penser honnêtement au nombre de cas **, mais cela peut être bien résumé en utilisant ** DP ** qui limite l'état. De plus, la condition ** $ K $ différente du déplacement précédent ** peut être considérée comme une transition.
($ t [i]: = $ ($ i $ jour de la main de l'adversaire), $ janken [i]: = $ (score obtenu en achetant avec $ i $ main))
Vous avez besoin d'informations sur le mouvement à effectuer pour le temps $ i $, et le DP peut être le suivant.
$ dp [i] [j]: = $ (score maximum lorsque vous déplacez $ j $ pour le $ i $ time)
De plus, la transition est la suivante (** je pensais correctement à la transition **, donc je suis resté coincé dans l'implémentation ici). De plus, Goo vaut 0, Choki vaut 1 et Par vaut 0. Notez également que ** l'initialisation ** se fait à $ i = $ 0 ~ $ k-1 $.
Si le premier coup $ i-k $ est $ l $, $ i $ le second coup est $ j $, alors ** $ l! =
(1) Si vous gagnez la $ i $ ème fois ... $ (j + 1) % 3 = t [i] $
(2) Si vous perdez ou tirez pour le temps $ i $
De plus, le score maximum que vous recherchez est ** $ mod \ k $ total , donc la réponse finale est $ 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()]
#Décidez en regardant la main immédiatement après
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:
#mise à jour
for j in range(3):
#Source de transition
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)
** Ce serait mieux si vous pouviez penser en ordre depuis la veille **, et ** la méthode gourmande semble être difficile ** (en fait, ce n'est pas si difficile).
(Dans ce qui suit, l'opération d'achat de toutes les actions ou de vente de toutes les actions est optimale, mais je ne vais pas le prouver ici.)
Si vous pensez normalement au montant maximum d'argent dont vous disposez le jour $ i $, il devient très difficile de déterminer si vous avez des actions ou non. Par conséquent, étant donné que ** vendez finalement tous les stocks **, le DP suivant peut être défini.
$ dp [i]: = $ (montant maximum d'argent dont vous disposez lors de la vente de toutes les actions le $ i $ jour)
À ce stade, si vous faites attention au moment où vous achetez toutes les actions, vous pouvez exprimer la transition comme suit: ** acheter toutes les actions le jour $ j $ **.
dp[i]=max(dp[i],(dp[j]//a[j])*a[i]+dp[j]%a[j])
De plus, le montant du calcul est de $ O (N ^ 2) $, ce qui est suffisant. Au début, j'essayais de le résoudre avec $ O (N) $, mais il ressort clairement des contraintes que $ O (N ^ 2) $ suffit.
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])
Je voudrais penser à une combinaison magique, mais ** il semble difficile de choisir goulûment **. ** Si vous gérez la puissance magique requise pour chaque force physique ** Cela a l'air bien et vous pensez à DP.
Il est bon de configurer le DP suivant.
$ dp [i]: = $ (Puissance magique minimale requise lorsque la force physique restante du monstre est $ i $)
A ce moment, la transition est simple, et si le pouvoir d'une certaine magie est $ a $ et le pouvoir de la magie est $ b $, ce sera comme suit.
De plus, ** magic peut être utilisée autant de fois que nécessaire **, vous pouvez donc calculer DP dans la direction de $ h \ rightarrow0 $.
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])
L'opération peut être ** paraphrasée ** en multipliant $ A \ _i, A \ _j $ par -1, donc elle peut être facilement résolue en classant les cas avec des nombres négatifs pairs ou impairs. Je vais.
Cependant, même un tel problème peut être poussé par DP. En effet, il est inutile d'effectuer chaque opération avec $ i $ plus d'une fois, il n'est donc nécessaire d'effectuer l'opération qu'une seule fois, et à ce moment ** les opérations peuvent être effectuées de manière monotone depuis l'avant **.
Le DP suivant doit être défini. (Bien que $ i $ et $ i + 1 $ soient sélectionnés dans l'opération dans l'énoncé du problème, l'opération pour sélectionner $ i-1 $ et $ i $ est l'opération $ i $ ème pour la commodité de l'implémentation. Je vais.)
$ dp [i] [j]: = $ (Valeur maximale du nombre total de colonnes lorsque l'opération jusqu'à la $ i $ ème opération est effectuée et que la $ i $ ème opération est effectuée (ou non effectuée))
Cependant, on suppose que $ j = 1 $ n'est pas exécuté et que $ j = 1 $ est exécuté.
De plus, la transition à ce moment est la suivante.
(1) En fonctionnement au i $ e $
Il convient de noter que ** $ i-1 $ que l'opération ait été effectuée ou non ** à ce moment-là est $ a [i-1] $ ou $ -a [i-1] $ changements. ** Faites attention à la différence **.
(2) Lorsqu'aucune opération n'est effectuée au $ i $ th
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]))
Il peut être divisé si seuls les voisins sont différents, et la sous-chaîne doit être aussi courte que possible pour se diviser davantage. À ce stade, même si la sous-chaîne d'une longueur de 3 ou plus est divisée, la condition du sujet peut être satisfaite, il doit donc s'agir de ** une chaîne de caractères d'une longueur de 1 ou 2 **. À ce stade, nous allons d'abord envisager d'utiliser une méthode gourmande qui rend les longueurs des sous-chaînes une par une autant que possible, mais vous n'êtes peut-être pas sûr de la légitimité que la mise en œuvre est un peu lourde. Dans ce cas, DP peut être utilisé pour ** AC ** de manière claire et légitime.
Découpez une sous-chaîne du caractère précédent afin que la longueur soit 1 autant que possible. La longueur est de 2 uniquement lorsque le caractère de longueur 1 est coupé juste avant et égal au caractère suivant. La mise en œuvre peut être effectuée en enregistrant la sous-chaîne qui a été coupée immédiatement avant.
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)
Vous pouvez ** limiter le nombre d'états **, en notant que vous ne pouvez en couper qu'un ou deux. Par conséquent, le DP peut être réglé comme suit.
$ dp [i] [j]: = $ ($ i $ th est ** le nombre maximum de divisions dans la chaîne de longueur $ j + 1 $)
De plus, la transition est la suivante, en considérant la transition vers $ dp [i] $. Ici, laissez le caractère $ i $ être $ s [i] $.
(1) Lorsque le $ i $ th est inclus dans une sous-colonne de longueur 1
Lorsque le $ i-1 $ th est inclus dans la sous-colonne de longueur 2, il peut être sélectionné sans condition, et $ dp [i] [0] = dp [i-1] [1] + 1 $. .. $ i-1 Lorsque le $ th est inclus dans une sous-colonne de longueur 1, $ s [i-1]! = S [i] $ quand $ dp [i] [0] = max (dp [i] [ 0], dp [i-1] [0] + 1) $.
(2) Lorsque le $ i $ th est inclus dans une sous-colonne de longueur 2
Lorsque le $ i-2 $ th est inclus dans une sous-colonne de longueur 1, il peut être sélectionné sans condition, et $ 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]))
Premièrement, il existe des combinaisons $ _ {16} C_2 $ de raccourcis. Tenez compte du nombre maximal de pressions sur les boutons requis pour chacune de ces combinaisons de raccourcis. Pour le moment, ** il est difficile de penser avec gourmandise **, et ** l'opération consistant à organiser les caractères dans l'ordre peut être considérée comme une transition **, vous pouvez donc penser à DP.
On suppose que la commande de raccourci est fixée à $ L, R $. À ce stade, réglez DP comme suit.
$ dp [i]: = $ (nombre minimum de fois où la commande est décidée jusqu'à $ i $)
La transition DP à ce moment est la suivante. Ici, j'ai considéré que le DP était passé du $ k $ th.
(1) Lorsque vous n'utilisez pas de raccourcis
(2) Lors de l'utilisation de raccourcis
Si le raccourci correspond aux caractères $ k + 1 $ et $ k + 2 $ ème ($ s [k + 1: k + 3] == l $ ou $ 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)
Au contraire, je pense qu'il vaut mieux ne pas sélectionner DP pour ce problème. En d'autres termes, vous pouvez prendre un ** point extrême **, qui remplit l'une des conditions suivantes:
De plus, vous devez être avide de remplir cette condition, et vous pouvez le faire avec la politique suivante.
Si la dernière note sélectionnée est $ x $ et que la note du point que vous recherchez est $ r \ _i $, les conditions de sélection de $ r \ _i $ sont l'une des suivantes.
Lorsque l'un ou l'autre de ces éléments tient, il peut être inclus dans le graphique du sujet, et vous pouvez sélectionner avidement les éléments un par un.
En outre, ** les notes de gauche et de droite peuvent être incluses car elles remplissent toujours les conditions du graphique **. Par conséquent, si le nombre de points inclus dans le graphique qui est sélectionné avec avidité est inférieur à 3, -1 doit être affiché, et s'il est égal ou supérieur à 3, le nombre de points doit être généré.
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