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 := 0; 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++: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
#define LL long long
#define FOR(i,a,b) for(int i=a;i<=b;++i)
 
using namespace std;
 
static const LL MAX_N = 1e+5;
static const LL INF = 1 << 25;
 
struct clothes{
    LL A[100],B[100],C[150];
};
 
int N,D;
LL res=-INF;
LL Day[300];
LL mem[300][150];
clothes T;
 
LL cal(LL day,LL p,LL pp,LL sum){
    //cout<<res<<" "<<day<<endl;
    if(day>2)  mem[day][p]=res;
    if(res<sum+abs(pp-p)&&day==N+1){
        return res=sum+abs(pp-p);
    }
    else if(mem[day][p]!=0){
           // cout<<"hoge"<<endl;
        return mem[day][sum+abs(pp-p)];
    }
    else{
        if(day==N+1)return 0;
        else if(day==0){
            FOR(i,1,D)
            if(Day[1]>=T.A[i]&&Day[1]<=T.B[i])cal(day+1,T.C[i],p,sum);
        }
        FOR(i,1,D){
            if(Day[day]>=T.A[i]&&Day[day]<=T.B[i]){
                if(day>2)cal(day+1,T.C[i],p,sum+abs(pp-p));
                else cal(day+1,T.C[i],p,sum);
            }
        }
    }
    return mem[day][p]=res;
}
 
 
int main(){
    cin>>N>>D;
    FOR(i,1,N)cin>>Day[i];
    FOR(i,1,D)
        cin>>T.A[i]>>T.B[i]>>T.C[i];
    cout<<cal(0,0,0,0)<<endl;
}

C++: #include <iostream>

using namespace std;

int main()
{
	int d, n;
	cin >> d >> n;
	int dp[201][201];
	int a[201], b[201], c[201], t[201];
	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 j = 0; j < d; j++)
		{
			dp[j][i] = 0;
		}
	}
	for (int i = 1; i < d; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (a[j] <= t[i] && t[i] <= b[j])
			{
				int ans = 0;
				for (int k = 0; k < n; k++)
				{
					if (c[j] >= c[k] && a[k] <= t[i - 1] && t[i - 1] <= b[k])
					{
						if (ans <= (dp[i - 1][k] + c[j] - c[k]))
						{
							ans = dp[i - 1][k] + c[j] - c[k];
						}
					}
					else if (c[j] < c[k] && a[k] <= t[i - 1] && t[i - 1] <= b[k])
					{
						if (ans <= (dp[i - 1][k] - c[j] + c[k]))
						{
							ans = dp[i - 1][k] - c[j] + c[k];
						}
					}
				}
				dp[i][j] = ans;
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		if (ans <= dp[d - 1][i])
		{
			ans = dp[d - 1][i];
		}
	}
	cout << ans << endl;
	return 0;
}

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

const int INF = 10001000;

int main(){

    //d := 日数 n := 服の種類
    int d, n; cin >> d >> n;
    vector<int> t(d);
    for(int i = 0; i < d; i++) cin >> t[i];
    vector<int> a(n);
    vector<int> b(n);
    vector<int> c(n);
    for(int i = 0; i < n; i++) cin >> a[i] >> b[i] >> c[i];

    vector<vector<int> > dp(d + 1, vector<int> (110, -INF));

    for(int i = 0; i < n; i++){

        //着れるなら
        if(a[i] <= t[0] && t[0] <= b[i]) dp[0][c[i]] = 0;
    }

    for(int i = 0; i < d - 1; i++){
        for(int j = 0; j <= 100; j++){

            if(dp[i][j] == -INF) continue;

            for(int k = 0; k < n; k++){

                //k番目の服を i 日目にきる
                if(a[k] <= t[i + 1] && t[i + 1] <= b[k]) dp[i + 1][c[k]] = max(dp[i + 1][c[k]], dp[i][j] + (int)abs(j - c[k]));
            
            }
        }
    }

    //cout << 30 << " " << 40 << " " << 60 << " " << 90 << endl;
    /*for(int i = 0; i < d - 1; i++){
        cout << dp[i][30] << " " << dp[i][40] << " " << dp[i][60] << " " << dp[i][90] << endl;
    }*/

    int ans = -INF;
    for(int i = 0; i <= 100; i++) ans = max(ans, dp[d - 1][i]);

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

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

#define MAX 210

#define pb push_back
#define mp make_pair

using namespace std;

int main(void)
{
	int d,n;
	int a,b,c;
	int i1,i2,i3;
	int maxx;

	cin>>d>>n;

	vector<int> t(d);
	vector<pair<int,int> > cl[MAX]; 

	for(i1=0;i1<d;i1++){
		cin>>t[i1];
	}
	for(i1=0;i1<n;i1++){
		cin>>a>>b>>c;
		
		for(i2=0;i2<d;i2++){
			if(a<=t[i2] && t[i2]<=b) cl[i2].pb(mp(c,0));
		}
	}

	maxx=0;
	for(i1=1;i1<d;i1++){

		for(i2=0;i2<cl[i1].size();i2++){
			for(i3=0;i3<cl[i1-1].size();i3++){
				cl[i1][i2].second=max(cl[i1][i2].second,abs(cl[i1][i2].first-cl[i1-1][i3].first)+cl[i1-1][i3].second);
				//cout<<cl[i1][i3].first<<" "<<" "<<cl[i1][i2].first<<" "<<cl[i1][i2].second<<endl;
			}
			maxx=max(maxx,cl[i1][i2].second);
		}
		//cout<<endl;
	}

	cout<<maxx<<endl;

	return 0;
}

C++: #include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define LL long long
static const LL INF = 1<<60;
static const int MAX_N = 300;
using namespace std;

struct clothes{
    LL A[MAX_N],B[MAX_N],C[MAX_N];
};


int N,D;
int Day[MAX_N];
LL res=-INF;
LL ans;
clothes T;

LL cal(int day,int pp){
   //cout<<ans<<" "<<res<<" "<<day-1<<" "<<pp<<endl;
   if(day==N+1){
        if(ans<res)ans=res;
        return 0;
   }
    FOR(i,1,D){
        if(Day[day]>=T.A[i]&&Day[day]<=T.B[i]){
            if(day<2)res=cal(day+1,T.C[i]);
            else {
                //cout<<abs(pp-T.C[i])<<endl;
                res=max(cal(day+1,T.C[i])+abs(pp-T.C[i]),res);
            }
        }
    }
   return ans;
}

int main(){
    cin>>N>>D;
    FOR(i,1,N){
        cin>>Day[i];
    }
    FOR(i,1,D){
        cin>>T.A[i]>>T.B[i]>>T.C[i];
    }
    cout<<cal(1,0)<<endl;
}

C++: #include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int D, N, T[212], A[212], B[212], C[212];
int memo[212][112];

int dp(int d, int b)
{
	if (memo[d][b] != -1) { return memo[d][b]; }
	int res = 0;
	rep(i, N)
	{
		if (A[i] <= T[i] && T[i] <= B[i]) { res = std::max(res, dp(d + 1, C[i]) + abs(b - C[i])); }
	}
	return memo[d][b] = res;
}

int main()
{
	memset(memo, -1, sizeof(memo));
	in >> D >> N;
	rep(i, D) { in >> T[i]; }
	rep(i, N) { in >> A[i] >> B[i] >> C[i]; }
	out << dp(0, 0) << std::endl;
	return 0;
}