今日はDPの神が降りてきている
自力で解いた
dp[i][j] iは日数 jは派手さとして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); public static void main(String[] args) { int d = sc.nextInt(); int n = sc.nextInt(); int[] t = new int[d]; for(int i = 0; i < d; i++) { t[i] = sc.nextInt(); } int[] a = new int[n]; int[] b = new int[n]; int[] c = new int[n]; for(int i = 0; i < n; i++) { a[i] = sc.nextInt(); b[i] = sc.nextInt(); c[i] = sc.nextInt(); } int[][] dp = new int[d][101]; for(int i = 0; i < d; i++) { Arrays.fill(dp[i], -1); } for(int i = 0; i < n; i++) { if(t[0] >= a[i] && t[0] <= b[i]) { dp[0][c[i]] = 0; } } for(int i = 1; i < d; i++) { for(int j = 0; j < n; j++) { if(t[i] >= a[j] && t[i] <= b[j]) { for(int k = 0; k < 101; k++) { if(dp[i-1][k] != -1) { dp[i][c[j]] = Math.max(dp[i-1][k] + Math.abs(k - c[j]), dp[i][c[j]]); } } } } } int max = 0; for(int i = 0; i < 101; i++) { max = Math.max(dp[d-1][i], max); } System.out.println(max); } }
Source: 12th Japanese Olympiad in Informatics, Preliminary Round , 2012-12-16
http://www.ioi-jp.org/