vov44k

DP with forbidden

Sep 18th, 2022
152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 0.73 KB | None | 0 0
  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.  
  5.     public static void main(String[] args){
  6.         Scanner in = new Scanner(System.in);
  7.         int n = in.nextInt();
  8.         int k = in.nextInt();
  9.         int l = in.nextInt();
  10.         boolean[] frog = new boolean[n];
  11.         for (int i = 0; i < l; i++) {
  12.             frog[in.nextInt() - 1] = true;
  13.         }
  14.         int[] Arr = new int[100000];
  15.         Arr[0] = 1;
  16.         if (!frog[1])
  17.             Arr[1] = 1;
  18.         for (int i = 2; i < n; i++) {
  19.             if (!frog[i]) {
  20.                 for (int j = Math.max(0, i - k); j < i; j++) {
  21.                     Arr[i] += Arr[j];
  22.                 }
  23.             }
  24.         }
  25.         System.out.println(Arr[n - 1]);
  26.     }
  27.  
  28. }
Advertisement
Add Comment
Please, Sign In to add comment