[AOJ] No. 0579 暑い日々 (Hot days)

2019年11月16日

問題

方針

\( i \) 日目に着ることができる服の派手さの最小値を \( v_i \), 最大値を \( w_i \) とします。各日において派手さの最小値または最大値を持つ服を選ぶことが最適なので、次の動的計画法を行います。証明はしていませんが、派手さを値をプロットすることで確認できると思います。

\( d(i, 0)\) を \( i \) 日目に最小値を持つ派手さの服を着た時の派手さの差の最大値とし、\( d(i, 1)\) を \( i \) 日目に最大値を持つ派手さの服を着た時の派手さの差の最大値とします。このとき、遷移は、次のようになります。

\[
\begin{eqnarray}
d(i + 1, 0) &=& \max (d(i, 0) + |v_{i + 1} – v_{i}|, d(i, 1) + |v_{i + 1} – w_i|)\\
d(i + 1, 1) &=& \max (d(i, 0) + |w_{i + 1} – v_{i}|, d(i, 1) + |w_{i + 1} – w_i|)
\end{eqnarray}
\]

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int D, N;
    cin >> D >> N;
    int T[D], A[N], B[N], C[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 x[D][2];
    for (int i = 0; i < D; i++) {
        x[i][0] = 101;
        x[i][1] = -1;
    }
    for (int i = 0; i < D; i++) {
        for (int j = 0; j < N; j++) {
            if (A[j] <= T[i] && T[i] <= B[j]) {
                x[i][0] = min(x[i][0], C[j]);
                x[i][1] = max(x[i][1], C[j]);
            }
        }
    }
    int dp[D][2]{};
    for (int i = 0; i < D - 1; i++) {
        dp[i + 1][0] = max(abs(x[i + 1][0] - x[i][0]) + dp[i][0], abs(x[i + 1][0] - x[i][1]) + dp[i][1]);
        dp[i + 1][1] = max(abs(x[i + 1][1] - x[i][0]) + dp[i][0], abs(x[i + 1][1] - x[i][1]) + dp[i][1]);
    }
    cout << max(dp[D - 1][0], dp[D - 1][1]) << "\n";
    return 0;
}