Lösen mit Ruby, Perl und Java AtCoder ABC 129 C (Teil 2) Dynamische Planungsmethode

Einführung

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

Dieses Thema

AtCoder Beginner Contest 129 C - Typical Stairs Difficulty: 795

• Teil 1 * Das Thema ist Fibonacci Das Thema des zweiten Teils ist die dynamische Planungsmethode Ruby Da die Kombination der Anzahl der Treppen gleich der Anzahl der Fibonacci war, könnte die Lösung des ersten Teils verwendet werden, aber ist es etwas, das universeller gelöst werden kann?

Hier kommt die dynamische Planungsmethode ins Spiel, die in * Offizielles Editorial * zu finden ist.

ruby.rb

n, m = gets.split.map(&:to_i)
MOD = 1_000_000_007
dp = Array.new(n + 2, 0)
a = []
dp[0] = 1
m.times do |i|
  a[i] = gets.to_i
  dp[a[i]] = -1
end
n.times do |i|
  next if dp[i] == -1
  if dp[i + 1] != -1
    dp[i + 1] += dp[i]
    dp[i + 1] %= MOD
  end
  if dp[i + 2] != -1
    dp[i + 2] += dp[i]
    dp[i + 2] %= MOD
  end
end
puts dp[n]

array.rb

  oks[a]=false;  # =>Anordnung von Bodenbrüchen

  dp[a[i]] = -1  # =>Boden gebrochen-1

Das offizielle Editorial bietet ein Array für defekte Böden, aber im Moment werden wir es in das DP-Array einbetten. Bei dem unten gezeigten Uhrentyp ist der Teil ** - 1 ** der gebrochene Boden. Wenn Sie das Debuggen mit VSCode usw. ausführen, wird das Innere des DP-Arrays in Variablen und Überwachungsausdrücken angezeigt, sodass Sie überprüfen können, wie sich der numerische Wert ändert und wie der fehlerhafte Boden übersprungen wird.

• VS-Codeeinstellungen für Ruby At Coder *
• VSCode-Einstellungen für Perls AtCoder (task.json) *

Fib-Version.rb

  if a[i] - a[i - 1] == 1
    puts "0"
    exit
  end

Die dynamische Planungsversion der Quelle enthält nicht den Teil der Fibonacci-Version, der bestimmt, ob der gebrochene Boden durchgehend ist. Nein, aber wenn es eine Reihe von kaputten Böden gibt, wird ** 0 ** ordnungsgemäß zurückgegeben.

Darüber hinaus ist es einfach, auf Änderungen der Bedingungen zu reagieren, z. B. auf drei Schritte.

Die dynamische Planungsmethode ist erstaunlich. Perl

perl.pl

chomp (my ($n, $m) = split / /, <STDIN>);
my $MOD = 1e9 + 7;
my (@a, @dp);
$dp[0] = 1;
for my $i (1..$m) {
  chomp (my $in = <STDIN>);
  $a[$i] = $in;
  $dp[$a[$i]] = -1;
}
for my $i (0..$n - 1) {
  next if $dp[$i] == -1;
  if ($dp[$i + 1] != -1) {
    $dp[$i + 1] += $dp[$i];
    $dp[$i + 1] %= $MOD;
  }
  if ($dp[$i + 2] != -1) {
    $dp[$i + 2] += $dp[$i];
    $dp[$i + 2] %= $MOD;
  }
}
print $dp[$n] + 0, "\n";

• Perl * nutzt die Tatsache aus, dass ein undefinierter Wert, der in der Berechnung verwendet wird, als ** 0 ** behandelt wird. Java

java.java

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());
        int MOD = 1_000_000_007;
        int a[] = new int[m];
        int dp[] = new int[n + 2];
        dp[0] = 1;
        for (int i = 0; i < m; i++) {
            a[i] = Integer.parseInt(sc.next());
            dp[a[i]] = -1;
        }
        sc.close();
        for (int i = 0; i < n; i++) {
            if (dp[i] == -1) {
                continue;
            }
            if (dp[i + 1] != -1) {
                dp[i + 1] += dp[i];
                dp[i + 1] %= MOD;
            }
            if (dp[i + 2] != -1) {
                dp[i + 2] += dp[i];
                dp[i + 2] %= MOD;
            }
        }
        System.out.print(dp[n]);
    }
}

Diesmal ist es eine Ergänzung, also AC </ font> ohne lange Verwendung.