yukicoder No.324 落ちてた閉路グラフ

問題文

解法

円状だと扱いづらいので、どこかを切って列の問題に帰着させよう。

列の場合の解法

0～n-1 の順に拾うかどうかを決めていくことにする。頂点 i を拾うと決めたとき、辺 i も拾うかどうかを知るには「頂点 i-1 を拾ったかどうか」の情報があれば十分。そのため次のような DP ができる。

dp[ i番目まで確定 ][ 拾った頂点の個数 ][ ひとつ前の頂点を拾ったか ] := このパターンの最大値

プログラムは次のように書く。

dpテーブルを -INF で初期化
dp[0][0][0] = 0
dp[0][1][1] = 0

for i in xrange(n - 1):
  for j in xrange(m + 1):
    for k in xrange(2):
      # i番目の頂点を拾わない
      chmax(dp[i + 1][j][0], dp[i][j][k])
      # i番目の頂点を拾う
      chmax(dp[i + 1][j + 1][1], dp[i][j][k] + k * w[i])
ans = -INF
for k in xrange(2):
  chmax(ans, dp[n - 1][m][k])
print ans

円状の場合の解法

円状の場合、0 番目と n-1 番目の頂点を繋ぐ辺も考慮する必要がある。これは 0 番目の頂点を拾ったかというフラグがあれば対処できる。

dp[ i番目まで確定 ][ 拾った頂点の個数 ][ ひとつ前の頂点を拾ったか ][ 0 番目の頂点を拾ったか ] := このパターンの最大値

プログラムの根幹は変わらない。0 番目と n-1 番目を繋ぐ辺の存在は ans の計算時だけ意識すればいい。

dpテーブルを -INF で初期化
dp[0][0][0][0] = 0
dp[0][1][1][1] = 0

for i in xrange(n - 1):
  for j in xrange(m + 1):
    for k in xrange(2):
      for l in xrange(2):
        # i番目の頂点を拾わない
        chmax(dp[i + 1][j][0][l], dp[i][j][k][l])
        # i番目の頂点を拾う
        chmax(dp[i + 1][j + 1][1][l], dp[i][j][k][l] + k * w[i])
ans = -INF
for k in xrange(2):
  for l in xrange(2):
    chmax(ans, dp[n - 1][m][k][l] + k * l * w[n - 1])
print ans

計算量は O(n²) 。

dp テーブルを使い回すようにしたら 579 ms から 162 ms にまで実行時間が落ちた。使いまわせる時は使いまわした方が良さそう。

yukicoder No.324 落ちてた閉路グラフ

割りと素直なDP問題だった。