aoj 0579 - Hot days

問題

問題概要

服を選んで、|Cx1 - Cx2| + |Cx2 - Cx3| + … + |Cxi-1 - Cxi| の最大値を求める問題。

解法

動的計画法で解ける。i日目までの服の選び方を決めたとき，i + 1日目以降について服を選んで目的の値を最大化する際には，1日目からi - 1日目までの服の選び方は関係ない。だから、dp[i日目][i日目に着た服の番号]という配列を作り、これをi=0から順番に埋めていく。また漸化式は
dp[i][k] = max(dp[i][k], dp[i - 1][j] + abs(c[k] - c[j]))　である。

ミス

dp配列の初期化をミスっていた。0初期化の部分

コード

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)

int main(void){
    int d, n;//日数　服の種類
    cin >> d >> n;
    vector<int> t(d);
    rep(i, d) cin >> t[i];
    vector<int> a(n), b(n), c(n);//最低　最大　派手さ
    rep(i, n) cin >> a[i] >> b[i] >> c[i];

    int dp[201][201];//dp[i][j] i(0~d-1)日目にj(0~n-1)番目の服を着た時の最大値
    rep(i, 201)rep(j, 201) dp[i][j] = -1;//初期化
    //0日目に着れる服のdpに0を入れる
    rep(j, d){
        if(a[j] <= t[0] && t[0] <= b[j]){
            dp[0][j] = 0;
        }
    }
    reps(i, 1, d){//日
        rep(j, n){//服の番号
            rep(k, n){//使える服を全探索で探しておく
                if(a[k] <= t[i] && t[i] <= b[k] && dp[i - 1][j] != -1){
                    dp[i][k] = max(dp[i][k], dp[i - 1][j] + abs(c[k] - c[j]));
                } 
            }
        }
    }


    int ans = 0;
    rep(i, n){
        ans = max(ans, dp[d - 1][i]);
    }
    printf("%d\n", ans);
    return 0;
}