■

JOI2012予選4「Hot Days」

解けたので、備忘録のため、コードを適当に貼ります（ひどい）。
コードの貼り方が分からないので、この記事は何回か更新されます。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int d, n;
int t[200];
int a[200], b[200], c[200];
int dp[201][200];			//dp[day][fuku] = sumの最大値
int ans = -1145141919;

void makeAns(){
	int day, fuku, i;
	
	//初期化
	for( day = 0; day < d + 1; day++ ){
		for( fuku = 0; fuku < n; fuku++ )
			dp[day][fuku] = -114514;
	}
	for( fuku = 0; fuku < n; fuku++ ){
		if( a[fuku] <= t[0] && t[0] <= b[fuku] )
			dp[1][fuku] = 0;	//0日目に服fukuを着た場合
	}
	
	//dp配列の更新
	for( day = 1; day < d; day++ ){
	for( fuku = 0; fuku < n; fuku++ ){
	//day日目の服を決める(遷移)
	for( i = 0; i < n; i++ ){
		if( a[i] <= t[day] && t[day] <= b[i] ){
			//day日目に服iを着る
			dp[day + 1][i] = max(dp[day + 1][i], dp[day][fuku] + abs(c[fuku] - c[i]));
		}
	}
	}
	}
	
	//答えを計算する
	for( i = 0; i < n; i++ ){
		ans = max(ans, dp[d][i]);
	}
}

int main()
{
	int i, j;
	cin >> d >> n;
	for( i = 0; i < d; i++ ) cin >> t[i];
	for( i = 0; i < n; i++ ) cin >> a[i] >> b[i] >> c[i];
	makeAns();
	cout << ans << endl;
	return 0;
}