AOJ 0288 Knocker of the Gigas Cedar

絶対DPの神様が降りてきてる

dp[i][j] i = 木の耐久力 j = 経験値

dp[i][j] = 最小回数

dp[Math.max(0, i - a[k])][Math.min(j + e[k], 100)] = Math.min(dp[Math.max(0, i - a[k])][Math.min(j + e[k], 100)], dp[i][j] + 1);

みたいな感じでDP

import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
  static Scanner sc = new Scanner(System.in);
  static PrintWriter out = new PrintWriter(System.out);
  static int INF = 2 << 25;
  public static void main(String[] args) {
    while(true) {
      int d = sc.nextInt();
      int n = sc.nextInt();
      if(d == 0 && n == 0) break;
      int[] a = new int[n];
      int[] e = new int[n];
      int[] r = new int[n];
      
      for(int i = 0; i < n; i++) {
        a[i] = sc.nextInt();
        e[i] = sc.nextInt();
        r[i] = sc.nextInt();
      }
      
      int[][] dp = new int[d+1][101];
      for(int i = d; i >= 0; i--) {
        Arrays.fill(dp[i], INF);
      }
      dp[d][0] = 0;
      for(int i = d; i >= 0; i--) {
        for(int j = 0; j <= 100; j++) {
          for(int k = 0; k < n; k++) {
            if(j >= r[k]) {
              dp[Math.max(0, i - a[k])][Math.min(j + e[k], 100)] = Math.min(dp[Math.max(0, i - a[k])][Math.min(j + e[k], 100)], dp[i][j] + 1);
            }
          }
        }
      }
      int min = INF;
      for(int i = 0; i < 101; i++) {
        min = Math.min(min, dp[0][i]);
      }
      if(min == INF) {
        System.out.println("NA");
      }
      else {
        System.out.println(min);
      }
      
    }

    
  }
}

Knocker of the Gigas Cedar | Aizu Online Judge

問題出典 PC Koshien 2013 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2013-11-9
http://web-ext.u-aizu.ac.jp/pc-concours/