JOI 12 本選 Hot days ( DP )
Hot days | Aizu Online Judge
dp[ i ][ j ]: After considering clothe for day i, which is of c_i = j, maximum value
#include <bits/stdc++.h> using namespace std; const int MAXD = 200 + 2; const int MAXN = 200 + 2; const int MAXT = 60 + 6; const int MAXAB = MAXT; const int MAXC = 100 + 2; void upmax(int &x, int v){ if( x < v ) x = v; } int d, n; int t[ MAXD ]; int a[ MAXN ], b[ MAXN ], c[ MAXN ]; int dp[ MAXD ][ MAXC ]; void solve(){ for(int i = 1; i <= d; ++i) for(int j = 0; j < MAXC; ++j) dp[ i ][ j ] = -(int)( 1e9 ); for(int i = 0; i < d; ++i) for(int j = 0; j < MAXC; ++j){ for(int k = 1; k <= n; ++k) if( a[ k ] <= t[ i + 1 ] && t[ i + 1 ] <= b[ k ] ){ if( i == 0 ) dp[ i + 1 ][ c[ k ] ] = 0; else upmax( dp[ i + 1 ][ c[ k ] ], dp[ i ][ j ] + abs( j - c[ k ] ) ); } } int ans = 0; for(int j = 0; j < MAXC; ++j) upmax( ans, dp[ d ][ j ] ); printf("%d\n", ans); } int main(){ scanf("%d%d", &d, &n); for(int i = 1; i <= d; ++i) scanf("%d", &t[ i ]); for(int i = 1; i <= n; ++i) scanf("%d%d%d", &a[ i ], &b[ i ], &c[ i ]); solve(); return 0; }