JOI 2012 - 暑い日々(問題4)

精進が必要だと思った問題．
dpだとは思っていましたが，鍛錬不足で全探索していた屑です．
前提として，C[n]をn番目の服の派手さとします．
i日目にj番目の服を着るときの価値の最大をdp[i][j]とします．
i-1日目にkという服を来たとして，
dp[i][j] = max(dp[i][j], dp[i-1][k]+abs(C[k]-C[j]))という漸化式を立てます．
あとはDPで解くだけです．

#include<iostream>
#include<algorithm>
#include<cmath>

struct Clothes{
	int max_t, min_t, value;
};

const int INF = 1 << 24, MAX_D = 201, MAX_N = 200;
int dp[201][200], t[201], cs[200][3];
//cs 0 max_t 1 min_t 2 派手さ

int main(){
	int d, n;
	std::cin >> d >> n;
	for(int i=1;i<=d;i++){
		std::cin >> t[i];
	}
	for(int i=0;i<n;i++){
		std::cin >> cs[i][0] >> cs[i][1] >> cs[i][2];
	}

	for(int i=1;i<=d;i++){
		std::fill(dp[i], dp[i]+n, -INF);
	}

	for(int i=0;i<n;i++){//１日目
		if(cs[i][0] <= t[1] && t[1] <= cs[i][1]){
			dp[1][i] = 0;
		}
	}

	int res = -INF;
	for(int i=2;i<=d;i++){//２日目以降
		for(int j=0;j<n;j++){
			if(cs[j][0] <= t[i] && t[i] <= cs[j][1]){
				for(int k=0;k<n;k++){
					dp[i][j] = std::max(dp[i][j],
															dp[i-1][k]+abs(cs[k][2]-cs[j][2]));
					res = std::max(res, dp[i][j]);
				}
			}
		}
	}

	std::cout << res << std::endl;
}