気持ち良く詰められた
問題概要
のオブジェに対し
- いずれかの列を選び、その列を一段沈める (このとき最下段ブロックは消える)
という操作を 回繰り返してオブジェを完全に消し去りたい。1 回の操作に要するコストは、そのブロックがその時点で左右に隣接している「マス目の色」が等しい箇所の個数である。
オブジェを消し去るのに必要な最小コストを求めよ。
制約
考えたこと
全探索では間に合わない。きっと何かしらの考察に基づいて、いい感じの順序を見出せるはず。たとえば「列を選んだら、一旦それを全消ししてよい」とかそういう考察が生えないかなと。。。でもそれは余裕で反例がある。
さて、王道に戻って、こういう問題はとりあえず の場合について考えて、それから一般の場合を考察するとよいことが多いと思う。そこで の考察を...と思った瞬間、そもそもこの問題は
- それぞれの隣接列について独立に解いて合計すればよい
ということがわかった。というのも、たとえば列 (a, b, c) があって、列 (a, b) についての最適順序と、列 (b, c) についての最適順序がわかっていたら、これらを上手く入れ子状に織り混ぜることで、双方の最適順序を達成できるからだ。
W = 2 に帰着
というわけで、問題は の場合に帰着された。そうはいっても、この時点ですでに の計算量がかかることになるから、せいぜい で解かなければならない。そのことを念頭において考察を進める。まず 2 つの文字列を とする。
とりあえずこんな DP を組みたくなる
- dp[ i ][ j ] := S が長さ i だけ残っていて、T が長さ j だけ残っている状態から出発して、最後まで埋めきるまでの最小コスト
こうしておくと、自然に次のような遷移が作れる
- chmin(dp[ i ][ j ], dp[ i - 1 ][ j ] + cost[ i ][ j ])
- chmin(dp[ i ][ j ], dp[ i ][ j - 1 ] + cost[ i ][ j ])
ここで cost[ i ][ j ] とは、S の長さ i の分と、T の長さ j の分とで、同じ要素が隣接している箇所の個数である。これは前処理で、累積和の要領であらかじめ求めてしまう。
#include <bits/stdc++.h> 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; vector<vector<int>> calcsame(string S, string T) { int N = S.size(); vector<vector<int>> res(N+1, vector<int>(N+1, 0)); for (int i = 0; i <= N; ++i) { res[i][0] = 0; for (int j = 0; i + j < N; ++j) { if (S[i+j] == T[j]) res[i+j+1][j+1] = res[i+j][j]+1; else res[i+j+1][j+1] = res[i+j][j]; } res[0][i] = 0; for (int j = 0; i + j < N; ++j) { if (S[j] == T[i+j]) res[j+1][i+j+1] = res[j][i+j]+1; else res[j+1][i+j+1] = res[j][i+j]; } } return res; } long long calccost(string S, string T) { int N = S.size(); const auto& cost = calcsame(S, T); //COUT(S); COUT(T); COUT(cost); vector<vector<long long>> dp(N+1, vector<long long>(N+1, INF)); dp[0][0] = 0; for (int l = 0; l <= N; ++l) { for (int r = 0; r <= N; ++r) { if (l) { chmin(dp[l][r], dp[l-1][r] + cost[l][r]); } if (r) { chmin(dp[l][r], dp[l][r-1] + cost[l][r]); } } } return dp[N][N]; } int main() { int H, W; cin >> H >> W; vector<string> fi(W, string(H, 'U')); for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) cin >> fi[j][i]; long long res = 0; for (int i = 0; i + 1 < fi.size(); ++i) { res += calccost(fi[i], fi[i+1]); } cout << res << endl; }