日記

のみろぐ

主に競プロ日記です

ABC040-C「柱柱柱柱柱」

ABC040-C「柱柱柱柱柱

解法

  • 「$dp[i]$:$i$手目の最小コスト」というDPテーブルを作る
  • 後はDPする


コード

集めるDP

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

using ll = long long;

const ll INF = 1e15;
int N;
ll a[111111];
ll dp[111111]; // dp[i]: i+1手目の最小コスト

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) { cin >> a[i]; }

    // DPテーブル初期化
    fill(dp, dp+N+10, INF);
    dp[0] = 0;

    // DP
    for (int i = 0; i < N; i++) {
       for (int j = 1; j <= 2; j++) {
          if (i >= j) {
             dp[i] = min(dp[i], dp[i-j] + abs(a[i-j] - a[i]));
          }
       }
    }
    cout << dp[N-1] << endl;

    return 0;
}

配るDP

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

using ll = long long;

const ll INF = 1e15;
int N;
ll a[111111];
ll dp[111111]; // dp[i]: i+1手目の最小コスト

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) { cin >> a[i]; }

    // DPテーブル初期化
    fill(dp, dp+N+10, INF);
    dp[0] = 0;

    // DP
    for (int i = 0; i < N; i++) {
       for (int j = 1; j <= 2; j++) {
          if (i + j < N) {
             dp[i+j] = min(dp[i+j], dp[i] + abs(a[i] - a[i+j]));
          }
       }
    }
    cout << dp[N-1] << endl;

    return 0;
}


感想

  • 1次元のDPは大体同じ書き方なんだなーと思った
    • 外側にDPテーブルの最後まで走査するループを書く
    • 内側に遷移のパターンを列挙する
    • この辺のことは1次元のDPもうちょっと解いてからまとめるつもり
  • なので書くことがそんなにない
  • ただ、配る・集めるのどちらが良いか?みたいなところは悩ましいと思う