けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Educational Codeforces Round 73 D. Make The Fence Great Again (R1700)

いかにも Greedy にできなさそうなので DP!!!

問題へのリンク

問題概要

長さ  N の整数数列  a_1, a_2, \dots, a_N が与えられる。今、数列の各項の値を整数分だけ増加させるなどして、数列のどの隣り合う二項も値が異なるようにしたい。

 i 項目を 1 増加させるのに要するコストは  b_i で与えられる。目的を達成するための最小コストを求めよ。

制約

  •  1 \le (クエリ数) \le 3 \times 10^{5}
  •  1 \le N \le 3 \times 10^{5}
  •  (N の総和) \le 3 \times 10^{5}

考えたこと

 O(N) で解ければ OK。こういうの、まずは Greedy に...とつい考えてしまう。しかし (2, 2, 3, 3) と並んでるところを、(3, 2, 4, 3) とか (2, 4, 3, 4) とかなんか色々なパターンが考えられて、やばそう

そこで DP できないか考えてみる。そしてちょっと考えると、

  • どの項も 3 以上増やす必要はない

ということがわかる。なぜなら、その項の左右の項がどのような状態であったとしても、

  • 「+0」 (そのまま)
  • 「+1」
  • 「+2」

の 3 種類のうちのどれかは被らずに生き残るからだ。よって「+3」するメリットはない。

DP へ

ここまでくれば、もうこの問題と一緒。

  • dp[ i ][ 0, 1, 2 ] := 最初の i 項について、最後の項を「+0」「+1」「+2」それぞれの場合についての、最小コスト

として DP すれば OK。

atcoder.jp

#include <iostream>
#include <vector>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL<<60;
int CASE;

int main() {
    cin >> CASE;
    while (CASE--) {
        int N; cin >> N;
        vector<long long> a(N), b(N);
        for (int i = 0; i < N; ++i) cin >> a[i] >> b[i];

        vector<vector<long long> > dp(N+1, vector<long long>(5, INF));
        dp[0][0] = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j <= 2; ++j) {
                for (int k = 0; k <= 2; ++k) {
                    if (i > 0 && a[i-1] + j == a[i] + k) continue;
                    chmin(dp[i+1][k], dp[i][j] + b[i] * k);
                }
            }
        }
        long long res = INF;
        for (int j = 0; j <= 2; ++j) chmin(res, dp[N][j]);
        cout << res << endl;
    }
}