introduction

J'écrirai un article de commentaire sur un problème qui a une méthode de solution de mensonge car il y a peu d'explications car c'est un vieux problème. En particulier, j'ai eu du mal car je ne trouvais pas l'explication dans le langage Python que j'utilisais sur le net. J'expliquerai à la fois le code source en langage Python.

problème

Énoncé du problème Entrée C-Command ARC002 Commentaire Commentaire officiel

Solution de mensonge

Énumérer L et R et remplacer avidement L ou R dans l'ordre. Dans cette solution, l'entrée est

  8
  ABABBABA

Il est expliqué dans le commentaire officiel que ce sera faux dans de tels cas. La bonne réponse est "4" car elle peut être LLRR si L = AB et R = BA. S'il s'agit d'une méthode de solution de mensonge, ce sera LLBLA ou ARBRR et sera "5". Cependant, comme un tel cas n'est pas inclus dans les items de test, il sera AC même avec la méthode de la solution lie.

Solution correcte

Comme indiqué dans le commentaire officiel, nous utilisons une planification dynamique. Je suis la i-ème lettre ・ (J = 0) Nombre de caractères lorsqu'il n'est pas remplacé par L, R ・ (J = 1) Nombre de caractères lors du remplacement par L ・ (J = 2) Nombre de caractères lors du remplacement par R J'ai fait 3 états et je l'ai résolu. Cette table dp est écrite comme dp [j] [i].

dp [0] [i] est la valeur obtenue en ajoutant +1 au nombre minimum de caractères à la fois avant un caractère.

dp[0][i]= min(dp[0][i-1],dp[1][i-1],dp[2][i-1])+1

Puisque dp [1] [i] et dp [2] [i] remplacent les caractères i-1 et i par L ou R, le nombre minimum de caractères jusqu'au caractère i-2 est augmenté de +1. Ce sera le nombre de caractères.

if c[i-2:i]==L:
  dp[1][i]=min(dp[0][i-2],dp[1][i-2],dp[2][i-2])+1

if c[i-2:i]==R:
  dp[2][i]=min(dp[0][i-2],dp[1][i-2],dp[2][i-2])+1

Si les caractères i-1 et i ne sont pas L et R et ne peuvent pas être remplacés ・ Copier dp [0] [i] Ou ・ Saisissez une valeur supérieure à la réponse (N ou float ("inf")) Laissons cela comme. Puisque la valeur minimale est prise par la méthode de planification dynamique, il n'y a pas de problème tant qu'il y a quelque chose de plus que dp [0] [i].

Exemple de code (Python)

N=int(input())
c=input()

L_list=["AA","AB","AX","AY","BA","BB","BX","BY","XA","XB","XX","XY","YA","YB","YX","YY"]
R_list=["AA","AB","AX","AY","BA","BB","BX","BY","XA","XB","XX","XY","YA","YB","YX","YY"]

ans=N
for L in L_list:
  for R in R_list:
    dp= [[0]*(N+1) for _ in range(3)]  #Bien que 0 soit attribué comme valeur initiale, il s'agit en fait d'une grande valeur ou du nombre de caractères.(i)Il est plus facile d'écrire après cela si vous remplacez

    for i in range(1,N+1):
      dp[0][i]= min(dp[0][i-1],dp[1][i-1],dp[2][i-1])+1
      if i==1:
        dp[1][i]= 1
        dp[2][i]= 1
      else:
        if c[i-2:i]==L:
          dp[1][i]=min(dp[0][i-2],dp[1][i-2],dp[2][i-2])+1
          dp[2][i]=N
        elif c[i-2:i]==R:
          dp[1][i]=N
          dp[2][i]=min(dp[0][i-2],dp[1][i-2],dp[2][i-2])+1
        else:
          dp[1][i]=N
          dp[2][i]=N

    tmp=min(dp[0][-1],dp[1][-1],dp[2][-1])
    ans=min(ans,tmp)

print(ans)

Liens connexes

Ceux qui rédigent des articles de commentaires en C ++ On peut oublier