CODE FESTIVAL 2016 qual C - D: Friction

問題

D: Friction - CODE FESTIVAL 2016 qual C | AtCoder

H\times Wのブロックがある。各ブロックは赤、緑、青のいずれかである。1度の操作で、一番下の行あるブロックのうち1つを消すことができる。消すときにかかるコストは、消した列の各ブロックの横に隣り合うブロックのうち色が同じ物の数のぶんだけかかる。全てのブロックを消すためのコストを最小化せよ。部分点はW=3の場合である。

  • 1\le H\le 300
  • 2\le W\le 300

解法

各列について消した数(or 高さ)を状態として持ってDPすることを考える。W=3であれば、

DP[H][H][H] := 全てのブロックを消すための最小コスト

となる。コストは別計算できないか考える。(0, 1)列目のペアと、(1, 2)列目のペアとで別々に計算する。消した数(or 高さ)を状態に持ち、そのブロックの状態でかかるコストを計算する。

h1[0列目の消した数][1列目の消した数], h2[1列目の消した数][2列目の消した数]

などとすればよい。あとは先程のDPの計算に組み込めばよい。ここまでで部分点が取れる。

ある列に対してかかるコストは隣接する列の状態のみに影響するので、列ごとに左から順に独立にコストを計算すれば十分であることが分かる。つまり、W=2の状態のみ応えられるようにして、これを左から順に足し合わせれば良い。このときコスト計算はDPする必要がある。コスト計算のDPは単純で「高さa, bで一致したら高さを両方進める」というように書く(LCSのように片方だけ進めるという式は不要)。隣接している列のどちらかが高さ0であれば0なので、これを初期状態とする。これにより、2列の高さのズレが考慮される。これで満点が取れる。

// 部分点解法(抜粋)
static int h1[303][303];
static int h2[303][303];

rep(a, H) rep(b, H) { // a[, b] := 0[, 1]列目を既に削った個数
  rep(k, H - max(a, b)) { // k := 下から数えてk番目
    h1[a][b] += (G[H-1-a-k][0] == G[H-1-b-k][1]);
    h2[a][b] += (G[H-1-a-k][1] == G[H-1-b-k][2]);
  }
}

static int dp[303][303][303];
rep(i, 303) rep(j, 303) rep(k, 303) dp[i][j][k] = inf;
dp[0][0][0] = 0;
rep(i, H + 1) rep(j, H + 1) rep(k, H + 1) {
  dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k] + h1[i][j]);
  dp[i][j+1][k] = min(dp[i][j+1][k], dp[i][j][k] + h1[i][j] + h2[j][k]);
  dp[i][j][k+1] = min(dp[i][j][k+1], dp[i][j][k] + h2[j][k]);
}
// 満点解法
int main() {

  int H, W;
  cin >> H >> W;
  vector<string> G(H);
  rep(i, H) cin >> G[i];

  ll ans = 0;

  rep(C, W - 1) {
    static int dp[303][303];
    static int h[303][303];
    rep(i, 303) rep(j, 303) h[i][j] = dp[i][j] = inf;
    rep(i, 303) h[0][i] = h[i][0] = 0;
    dp[0][0] = 0;

    rep(a, H) rep(b, H) {
      h[a+1][b+1] = min(h[a+1][b+1], h[a][b] + (G[a][C] == G[b][C+1]));
    }

    rep(i, H + 1) rep(j, H + 1) {
      dp[i+1][j] = min(dp[i+1][j], dp[i][j] + h[H - i][H - j]);
      dp[i][j+1] = min(dp[i][j+1], dp[i][j] + h[H - i][H - j]);
    }
    ans += dp[H][H];
    ans %= MOD;
  }

  cout << ans << endl;

  return 0;
}