Résolution avec Ruby, Perl et Java AtCoder ABC 129 C (Partie 2) 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 129 C - Typical Stairs Difficulty: 795

• Partie 1 * Le thème est Fibonacci Le thème de la deuxième partie est la méthode de planification dynamique Ruby Puisque la combinaison du nombre d'escaliers était égale au nombre de Fibonacci, la solution de la première partie pourrait être utilisée, mais est-ce quelque chose qui peut être résolu plus universellement?

C'est là que la méthode de planification dynamique trouvée dans * Éditorial officiel * entre en jeu.

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;  # =>Disposition des planchers cassés

  dp[a[i]] = -1  # =>Plancher cassé-1

L'éditorial officiel fournit un tableau pour les sols cassés, mais pour l'instant, nous allons l'intégrer dans le tableau DP. Dans le type de montre illustré ci-dessous, la partie ** - 1 ** est le plancher cassé. Lorsque vous exécutez le débogage avec VSCode, etc., l'intérieur du tableau DP est affiché dans des variables et des expressions de surveillance, afin que vous puissiez vérifier comment la valeur numérique change et comment ignorer le plancher cassé.

• Paramètres VS Code pour Ruby At Coder *
• Paramètres VSCode pour AtCoder de Perl (tasks.json) *

version fib.rb

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

La version de planification dynamique de la source n'a pas la partie de la version de Fibonacci qui détermine si le plancher rompu est continu. Non, mais s'il y a une série de planchers cassés, il renvoie correctement ** 0 **.

De plus, il est facile de répondre à des changements de conditions comme le fait de pouvoir monter trois marches.

La méthode de planification dynamique est incroyable. 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 * tire parti du fait que si une valeur non définie est utilisée dans le calcul, elle sera traitée comme ** 0 **. 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]);
    }
}

Cette fois, c'est un ajout, donc c'est AC </ font> sans utiliser long.