Go: ///
// File:  0579.go
// Author: ymiyamoto
//
// Created on Mon Mar 19 18:46:50 2018
//
package main

import (
	"fmt"
)

var D, N int

type cloth struct {
	A, B, C int
}

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func main() {
	fmt.Scan(&D, &N)
	thermals := make([]int, D+1)

	for i := 1; i <= D; i++ {
		fmt.Scan(&thermals[i])
	}

	clothes := make([]cloth, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&clothes[i].A, &clothes[i].B, &clothes[i].C)
	}

	dp := make([][]int, D+1)
	for i := range dp {
		dp[i] = make([]int, N)
	}

	for i := 1; i < D; i++ {
		for j := 0; j < N; j++ {
			for k := 0; k < N; k++ {
				t1 := thermals[i]
				t2 := thermals[i+1]
				if clothes[j].A <= t2 && t2 <= clothes[j].B && clothes[k].A <= t1 && t1 <= clothes[k].B {
					dp[i+1][j] = max(dp[i+1][j], dp[i][k]+abs(clothes[j].C-clothes[k].C))
				}
			}
		}
	}

	val := 0
	for _, v := range dp[D] {
		val = max(val, v)
	}

	fmt.Println(val)
}

C++: #include <bits/stdc++.h>
using namespace std;

int main() {
    int D, N, t[205], a[205], b[205], c[205], dp[205][205];  // dp[i][j] = i日目に服jを着た時の最大値
    cin >> D >> N;
    for(int i=0;i<D;i++){
        cin >> t[i];
    }
    for(int i=0;i<N;i++){
        cin >> a[i] >> b[i] >> c[i];
    }
    for(int i=0;i<D-1;i++){
        for(int j=0;j<N;j++){
            if(t[i] < a[j] || t[i] > b[j]) continue;
            for(int k=0;k<N;k++){
                if(t[i+1] < a[k] || t[i+1] > b[k])continue;
                dp[i+1][k] = max(dp[i+1][k], dp[i][j] + abs(c[k]-c[j]));
            }
        }
    }
    int ans = 0;
    for(int i=0;i<N;i++){
        ans = max(ans, dp[D-1][i]);
    }
    cout << ans << endl;
    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

struct Cloth
{
	int mini, maxi, glitz;
	bool operator<(const Cloth& c) const
	{
		if (this->glitz < c.glitz) return true;
		else if (this->glitz == c.glitz){
			if (this->mini < c.mini) return true;
			else if (this->mini == c.mini && this->maxi < c.maxi) return true;
			return false;
		}
		return false;
	}
};

int d, n;
int temp[256];
Cloth cloth[256];
int memo[256][256];

int solve(int day, int before);

int main()
{
	scanf("%d %d", &d, &n);
	for (int i = 1; i <= d; i++) scanf("%d", temp + i);
	for (int i = 1; i <= n; i++){
		scanf("%d %d %d", &cloth[i].mini, &cloth[i].maxi, &cloth[i].glitz);
	}
	cloth[0] = cloth[1];
	//sort(cloth, cloth + n);
	memset(memo, -1, sizeof(memo));
	
	solve(1, 0);
	/*
	for (int i = 1; i <= d; i++){
		for (int j = 1; j <= n; j++){
			printf("%d ", memo[i][j]);
		}
		puts("");
	}
	*/
	int sum = 0;
	for (int i = 1; i <= d; i++){
		int maxi = INT_MIN;
		for (int j = 1; j <= n; j++){
			maxi = max(maxi, memo[i][j]);
		}
		sum += maxi;
	}
	printf("%d\n", sum);
	return 0;
}

int solve(int day, int before)
{
	if (day > d) return cloth[before].glitz;
	if (memo[day][before] >= 0) return memo[day][before];
	
	int t = 0;
	for (int i = 1; i <= n; i++){
		if (cloth[i].mini <= temp[day] && temp[day] <= cloth[i].maxi){
			memo[day][i] = 0;
			//printf("%*d %d\n", day, day, i);
			t += abs(cloth[before].glitz - solve(day + 1, i));
		}
	}
	
	return memo[day][before] = t;
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

struct cl{
	int min;
	int max;
	int f;
};

int DP[500][200]; // DP[i][j] : ?????\?????????????´?????????????????????????????????§???

int main(){
	
	int D, N, ans;
	
	cin >> D >> N;
	
	int d[500];
	
	cl cloth[500];
	
	for(int i = 1; i <= D; i++){
		cin >> d[i];
	}
	
	for(int i = 0; i < N; i++){
		cin >> cloth[i].min >> cloth[i].max >> cloth[i].f;
	}
	
	for(int i = 0; i <= D; i++){
		for(int j = 0; j <= 100; j++){
			DP[i][j] = -(1 << 30);
		}
	}
	
	DP[0][0] = 0;
	
	for(int i = 1; i <= D; i++){
		for(int j = 0; j < N; j++){
			if(cloth[j].min <= d[i] && cloth[j].max >= d[i]){
				for(int k = 0; k <= 100; k++){
					if(k - cloth[j].f >= 0){
						DP[i][k] = max(DP[i][k], DP[i - 1][k - cloth[j].f] + cloth[j].f);
					}
					if(k + cloth[j].f <= 100){
						DP[i][k] = max(DP[i][k], DP[i - 1][k + cloth[j].f] + cloth[j].f);
					}
				}
			}
		}
	}
	
	ans = -(1 << 30);
	
	/*
	for(int i = 1; i <= D; i++){
		for(int j = 0; j <= 100; j++){
			if(DP[i][j] < 0){
				printf("0 ");
			}else{
				printf("%d ", DP[i][j]);
			}
		}
		printf("\n");
	}
	*/
	for(int j = 0; j <= 100; j++){
		if(DP[D][j] > ans){
			ans = DP[D][j];
		}
	}
	
	printf("%d\n", ans);
	
	return 0;
}

C++: #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;

#define int long long

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define rep(i,x) for(int i=0;i<(x);++i)
#define rep1(i,x) for(int i=1;i<=(x);++i)
#define rrep(i,x) for(int i=(x)-1;i>=0;--i)
#define rrep1(i,x) for(int i=(x);i>=1;--i)
#define FOR(i,a,x) for(int i=(a);i<(x);++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

#define omajinai ios::sync_with_stdio(false);cin.tie(0)

template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T get(){T a;cin>>a;return a;}
template<typename T>T rev(T a){reverse(all(a));return a;}
template<typename T>istream&operator>>(istream&is,vector<T>&vec){rep(i,vec.size())is>>vec[i];return is;}
template<typename T>vector<T>&sort(vector<T>&a){sort(all(a));return a;}

const int inf = 1e9;
const ll linf = 3e18;
const double eps = 1e-9;

int T[200], A[200], B[200], C[200];

int dp[201][200];

signed main()
{
    int D, N; cin >> D >> N;

    rep(i, D) {
        cin >> T[i];
    }

    rep(i, N) {
        cin >> A[i] >> B[i] >> C[i];
    }

    for (int i = 1; i < D; ++i) {
        rep(j, N) {
            if (T[i - 1] < A[j] || T[i - 1] > B[j]) continue;

            rep(k, N) {
                if (T[i] < A[k] || T[i] > B[k]) continue;

                chmax(dp[i][k], dp[i - 1][j] + abs(C[j] - C[k]));
            }
        }
    }

    int ans = 0;

    rep(i, D + 1) rep(j, N) chmax(ans, dp[i][j]);

    cout << ans << endl;
}