Résolution avec Ruby et Python AtCoder ABC011 C Méthode de planification dynamique

introduction

• Problèmes AtCoder * Utilise les recommandations pour résoudre les problèmes passés. Merci à AtCoder et AtCoder Problems.

Ce thème

• AtCoder Beginner Contest C - 123 soustraction * Difficulty: 761

Ce thème, méthode de planification dynamique

Il est similaire à la planification dynamique * AtCoder ABC 129 C en Ruby, Perl et Java (Partie 2) précédemment résolue *.

Sauter 1,2 étapes-> Soustraire 1,2,3

Ruby

ruby.rb

n = gets.to_i
a = Array.new(n + 1, n)
b = Array.new(n + 1, 101)
b[n] = 0
3.times do
  ng = gets.to_i
  a[ng] = -1 if ng <= n
end
n.downto(1) do |i|
  if a[i] > 0
    if i - 1 >= 0 && a[i - 1] > 0 && a[i] - 1 >= 0
      a[i - 1] = a[i] - 1
      b[i - 1] = b[i] + 1 if b[i - 1] > b[i] + 1
    end
    if i - 2 >= 0 && a[i - 2] > 0 && a[i] - 2 >= 0
      a[i - 2] = a[i] - 2
      b[i - 2] = b[i] + 1 if b[i - 2] > b[i] + 1
    end
    if i - 3 >= 0 && a[i - 3] > 0 && a[i] - 3 >= 0
      a[i - 3] = a[i] - 3
      b[i - 3] = b[i] + 1 if b[i - 3] > b[i] + 1
    end
  end
end
puts b[0] < 101 ? "YES" : "NO"

array.rb

a = Array.new(n + 1, n)
b = Array.new(n + 1, 101)

Préparez une table de soustraction et une table pour réduire le nombre de fois.

ans.rb

puts b[0] < 101 ? "YES" : "NO"

Oui / Non est jugé en regardant le nombre de fois où il devient «0».

En passant, dans le cas de la soustraction, le traitement lorsque l'argument devient négatif est inclus, donc cela semble compliqué. J'ai donc également écrit une version plus.

rubyplus.rb

n = gets.to_i
a = Array.new(n + 4, n)
b = Array.new(n + 4, 101)
b[0] = 0
3.times do
  ng = gets.to_i
  a[ng] = -1 if ng <= n
end
n.times do |i|
  if a[i] > 0
    1.upto(3) do |j|
      if a[i + j] > 0
        a[i + j] = a[i] + j
        b[i + j] = b[i] + 1 if b[i + j] > b[i] + 1
      end  
    end
  end
end
puts b[n] < 101 ? "YES" : "NO"

array.rb

a = Array.new(n + 4, n)
b = Array.new(n + 4, 101)

Cela correspond à un long tableau. Python

python.py

from sys import stdin

def main():
    input = stdin.readline
    n = int(input())
    a = [n] * (n + 4)
    b = [101] * (n + 4)
    b[0] = 0
    for i in range(3):
        ng = int(input())
        if ng <= n:
            a[ng] = -1
    for i in range(n):
        if a[i] > 0:
            for j in range(1, 4):
                if a[i + j] > 0:
                    a[i + j] = a[i] + j
                    if b[i + j] > b[i] + 1:
                        b[i + j] = b[i] + 1
    print("YES" if b[n] < 101 else "NO")
main()

Python est une version plus.

Résumé

• ABC 011 Résolu C
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Python