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++: //Name: Hot days
//Level: 3
//Category: 動的計画法,DP
//Note:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Cloth {
    int low, high;
    int cost;

    bool suitable(int temp) const {
        return low <= temp && temp <= high;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int D, N;
    cin >> D >> N;
    vector<int> temps(D);
    vector<Cloth> clothes(N);
    for(int i = 0; i < D; ++i) {
        cin >> temps[i];
    }
    for(int i = 0; i < N; ++i) {
        Cloth &cloth = clothes[i];
        cin >> cloth.low >> cloth.high >> cloth.cost;
    }

    vector<int> dp[2];
    dp[0].resize(N, 0);
    dp[1].resize(N, 0);
    for(int i = 1; i < D; ++i) {
        const int temp = temps[i];
        fill(dp[1].begin(), dp[1].end(), 0);
        for(int j = 0; j < N; ++j) {
            if(!clothes[j].suitable(temp)) continue;
            for(int prev = 0; prev < N; ++prev) {
                if(clothes[prev].suitable(temps[i-1])) {
                    dp[1][j] = max(dp[1][j], dp[0][prev] + abs(clothes[j].cost - clothes[prev].cost));
                }
            }
        }
        dp[0].swap(dp[1]);
    }

    cout << *max_element(dp[0].begin(), dp[0].end()) << endl;
    return 0;
}

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

using namespace std;

int dp[200][200] = {};
int INF = -99999999;

int main(){
	int D, N;
	int T[200] = {};
	int A[200] = {}, B[200] = {}, C[200] = {};

	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; i++){
		for (int j = 0; j < N; j++){
			if (i == 0){
				if (A[j] < T[i] && T[i] < B[j]){
					dp[i][j] = C[j];
				}
				else{
					dp[i][j] = INF;
				}
			}
			else if (i == 1){
				if (A[j] <= T[i] && T[i] <= B[j]){
					int tmp1 = INF;
					for (int k = 0; k < N; k++){
						int tmp2 = abs(dp[i - 1][k] - C[j]);
						if (tmp1 < tmp2 && dp[i-1][k]>=0){
							tmp1 = tmp2;
						}
					}
					dp[i][j] = tmp1;
				}
				else{
					dp[i][j] = INF;
				}
			}
			else{
				if (A[j] <= T[i] && T[i] <= B[j]){
					int tmp1 = INF;
					for (int k = 0; k < N; k++){
						int tmp2 = dp[i-1][k]+abs(C[j] - C[k]);
						if (tmp1 < tmp2 && dp[i - 1][k]>=0){
							tmp1 = tmp2;
						}
					}
					dp[i][j] = tmp1;
				}
				else{
					dp[i][j] = INF;
				}
			}
		}
	}
	/*
	for (int i = 0; i < D; i++){
		for (int j = 0; j < N; j++){
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
	*/
	int tmp = 0;
	for (int i = 0; i < N; i++){
		if (tmp < dp[D - 1][i]){
			tmp = dp[D - 1][i];
		}
	}

	cout << tmp << endl;
	
}

C++: #include <iostream>
#include <cmath>
using namespace std;

int main(){
	int D,N;
	int Kion[200];
	int Fmin[200],Fmax[200],Fhad[200];
	cin>>D>>N;
	for(int i=0;i<D;i++){
		cin>>Kion[i];
	}
	for(int i=0;i<N;i++){
		cin>>Fmin[i]>>Fmax[i]>>Fhad[i];
	}

	int Kekka[200][200];
	int rinji,rin2;
	//1??\???
	for(int i=0;i<N;i++){
		if(Kion[0]>=Fmin[i]&&Kion[0]<=Fmax[i]) Kekka[0][i]=0;
		else Kekka[0][i]=-1;
	}
	//2??\?????\???
	for(int day=1;day<D;day++){
		for(int fuku=0;fuku<N;fuku++){
			if(Kion[day]>=Fmin[fuku]&&Kion[day]<=Fmax[fuku]){
				rinji=-1;rin2=0;
				for(int mf=0;mf<N;mf++){
					if(Kekka[day-1][mf]!=-1&&rinji<=abs(Fhad[mf]-Fhad[fuku])) {rinji=abs(Fhad[mf]-Fhad[fuku]);rin2=mf;}
				}
				Kekka[day][fuku]=Kekka[day-1][rin2]+rinji;
			}
			else{
				Kekka[day][fuku]=-1;
			}
		}
	}
	rinji=0;
	for(int i=0;i<N;i++){
		rinji=max(rinji,Kekka[D-1][i]);
	}
	cout<<rinji<<endl;
	return 0;
}

C++: #include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int dayn,clothn;
    int dayC[200],clothI[3][200];
    int DP[200][200]={0};
    int sum,ans=0;
    scanf("%d%d",&dayn,&clothn);
    for(int i=0;i<dayn;i++)
        scanf("%d",&dayC[i]);
    for(int i=0;i<clothn;i++){
        for(int j=0;j<3;j++)
            scanf("%d",&clothI[j][i]);
    }
    for(int i=1;i<dayn;i++){
        for(int j=0;j<clothn;j++){
            for(int k=0;k<clothn;k++){

                /*
                for(int di=0;di<dayn;di++){
                    for(int dj=0;dj<clothn;dj++){
                        printf("%d ",DP[di][dj]);
                    }
                    puts("");
                }
                puts("-------");
                */

                if(clothI[0][j]<=dayC[i]&&dayC[i]<=clothI[1][j]&&clothI[0][k]<=dayC[i-1]&&dayC[i-1]<=clothI[1][k]){
                    sum=clothI[2][k]-clothI[2][j];
                    if(sum<0)
                        sum*=-1;
                    DP[i][j]=max(DP[i][j],DP[i-1][k]+sum);
                }
            }
        }
    }
    for(int i=0;i<clothn;i++){
        ans=max(ans,DP[dayn-1][i]);
    }
    printf("%d\n",ans);
    return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <sstream>
#include <cmath>

#define INT32_MAX 2147483647

using namespace std;

struct cloth {
    int min,max,c;

    bool operator<(const cloth& right) const {
        return c < right.c;
    }
};


int t[201];
cloth clothes[201];

inline bool isrange(int temp, cloth *c) {
    return (c->min <= temp) && (temp <= c->max);
}

int main() {
    int d,n;
    cin >> d >> n;
    for (int i = 0; i < d; ++i) {
        cin >> t[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> clothes[i].min >> clothes[i].max >> clothes[i].c;
    }
    sort(clothes, clothes + n);

    int result = 0;
    int prec;
    for (int j = 0; j < n; ++j) {
        if (!isrange(t[0], &clothes[j])) continue;

        prec = clothes[j].c;
        break;
    }

    for (int i = 1; i < d; ++i) {
        if ((i % 2) == 0) {
            for (int j = 0; j < n; ++j) {
                if (!isrange(t[i], &clothes[j])) continue;

                result += abs(prec - clothes[j].c);
                prec = clothes[j].c;
                break;
            }
        } else {
            for (int j = n - 1; 0 <= j; --j) {
                if (!isrange(t[i], &clothes[j])) continue;

                result += abs(prec - clothes[j].c);
                prec = clothes[j].c;
                break;
            }
        }
    }

    cout << result << endl;

    return 0;
}

C++: #include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int memo[201][201];
int d, n;
int t[200];
int a[200], b[200], c[200];

int rec(int k, int prev){
	
	if(memo[k][prev] != -1)return memo[k][prev];
	if(k == d)return 0;
	
	int best = 0;
	for(int next = 0; next < n; next++){
		if(t[k] >= a[next] && t[k] <= b[next])
			best = max(best, rec(k + 1, next) + abs(c[next] - c[prev]));
	}
		
	return memo[k][prev] = best;
		
}
int main() {
	for(int i = 0; i <= 200; i++)
		for(int j = 0; j <= 200; j++)
			memo[i][j] = -1;
			
	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];
		
	int ans = 0;
	for(int i = 0; i < n; i++){
		ans = rec(0, i);
	}

	
	cout << ans << endl;
	
	return 0;
}