いかにも Greedy にできなさそうなので DP!!!
問題概要
長さ の整数数列 が与えられる。今、数列の各項の値を整数分だけ増加させるなどして、数列のどの隣り合う二項も値が異なるようにしたい。
項目を 1 増加させるのに要するコストは で与えられる。目的を達成するための最小コストを求めよ。
制約
考えたこと
で解ければ 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。
#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; } }