Lösen mit Ruby und Python AtCoder ABC011 C Dynamische Planungsmethode

Einführung

• AtCoder-Probleme * Verwenden Sie Empfehlungen, um frühere Probleme zu lösen. Dank AtCoder und AtCoder Probleme.

Dieses Thema

• Subtraktion des AtCoder-Anfängerwettbewerbs C - 123 * Difficulty: 761

Dieses Thema, dynamische Planungsmethode

Es ähnelt dem zuvor gelösten * AtCoder ABC 129 C in Ruby, Perl und Java (Teil 2) Dynamische Planung *.

Springe 1,2 Schritte-> Subtrahiere 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)

Bereiten Sie eine Subtraktionstabelle und eine Tabelle vor, um die Anzahl der Male zu reduzieren.

ans.rb

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

Ja / Nein wird anhand der Häufigkeit beurteilt, mit der es zu "0" wird.

Übrigens ist im Fall der Subtraktion die Verarbeitung, wenn das Argument negativ wird, enthalten, so dass es sich kompliziert anfühlt. Also habe ich auch eine Plus-Version geschrieben.

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)

Es entspricht einem langen Array. 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 ist eine Plus-Version.

Zusammenfassung

• ABC 011 Gelöst C.
• Machen Sie sich mit Ruby vertraut
• Machen Sie sich mit Python vertraut