絶対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/