AOJ 0579 Hot days

今日は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);

    
  }
}

Hot days | Aizu Online Judge

Source: 12th Japanese Olympiad in Informatics, Preliminary Round , 2012-12-16
http://www.ioi-jp.org/