読者です 読者をやめる 読者になる 読者になる

基礎的な動的計画法(5題)

プログラミングコンテストチャレンジブック [第2版] ~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~
いわゆる「蟻本」である。この章末で紹介されている練習問題をひたすら解いている。
今回は基礎的な動的計画法。基礎的といっても最後の問題とか難しかったから他の人の解法を見た...

dpをうまく定義することと、漸化式を正しく作ること、これに尽きる。
dpを定義する着想は深さ優先探索っぽく最初は考えて、これdpにしたらどうなるの?っていう順番で考えると思いつきやすいかも。

POJ3176 Cow Bowling

3176 -- Cow Bowling

問題概要

0以上99以下の数字をピンにしてボーリングをする
例:5列のピン
7
3 8
8 1 6
2 8 4 4
4 5 2 6 5
ボールがこのピンを通過する。いちばん上から始めて、下の二つの数のどちらかに下っていき、一番下の列まで行く。通過した数字の合計が点数となる。N (1 <= N <= 350) 350)列のピンが与えられるので、可能な点数の最大値を求めよ。

解法

動的計画法で下の列からdpを埋めていく。

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
  // 入力
  int N;
  cin >> N;
  vector< vector<int> >  pin(N, vector<int>(N) );
  vector< vector<int> >  dp(N, vector<int>(N) );
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= i; j++) {
      cin >> pin[i][j];
    }
  }
  // 動的計画法。ボトムアップ
  for (int j = 0; j < N; j++) {
    dp[N-1][j] = pin[N-1][j];
  }
  if (N == 1) {
    cout << dp[0][0] << endl;
    return 0;
  }
  // N >= 2
  for (int i = N - 2; i >= 0; i--) {
    for (int j = 0; j <= i; j++) {
      dp[i][j] = pin[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
    }
  }

  // 出力
  cout << dp[0][0] << endl;
}

POJ2229: Sumsets

2229 -- Sumsets

問題概要

整数Nを2のべき乗によって表される整数(1,2,4,8,16,...)の和で表すのは何通りが可能か。
1 <= N <= 1000000
例:
5 = 1+1+1+1+1
= 1+1+1+2
= 1+2+2
= 1+4
なので、5は4通りである。

解法

整数mがdp[m]通りの和で表せるとする。例をたくさん書き出してみると、漸化式が作れることがわかる。
mの偶奇によって漸化式が変わる。
mが奇数のとき: dp[m] = dp[m-1]
mが偶数のとき: dp[m] = dp[m-1] + dp[m/2]
この漸化式が正しいことも証明しておこう。
mが奇数のとき:
mを2のべき乗の和で表すと、少なくとも1つは1がある。つまり、
m = 1 + (2のべき乗の和の形)
という形になるが、この式の(2のべき乗の和の形)はdp[m-1]通りある。
よって、dp[m] = dp[m-1]が成り立つ。
mが偶数のとき:
mを2のべき乗の和で表す方法は次の2通りである。
m = 1 + (2のべき乗の和の形)
m = 2 * (2のべき乗の和の形) (式全体を2でくくった)
第一の式は1が含まれる場合で、第二の式は1が含まれない場合であるから、両者に重複はない。第一式はdp[m-1]通り。第二式はdp[m/2]通り。
よって、dp[m] = dp[m-1] + dp[m/2] が成り立つ。

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
const int MAX = 1000000000;

int main() {
  int N;
  cin >> N;
  vector<unsigned long long> dp(N);
  dp[1] = 1;
  for (int i = 2; i <= N; i++) {
    // 偶奇で場合分け
    dp[i] = (i % 2 == 0) ? dp[i-1] + dp[i/2] : dp[i-1];
    dp[i] %= MAX;
  }
  cout << dp[N] << endl;
}

POJ2385: Apple Catching

2385 -- Apple Catching

問題概要

毎分、2本の木のどちらかからりんごが落ちる。ベシーは毎分、どちらかのりんごの木の下にいて、落ちてくるりんごをキャッチできる。ベシーが2本の木の間を移動する回数はW回(1 <= W <= 30)以下である。りんごはT分間(1 <= T <= 1000)落ちる。毎分、どの木からりんごが落ちるかデータが与えられたときに、ベシーがキャッチできるりんごの最大数を求めよ。最初、ベシーは木1にいる。

解法

動的計画法
dp[i][j] = (i分までにちょうどj回移動したときに得られるりんごの最大数)
とする。
dp[1][0] = 1, dp[1][1] = 0 である。
これを計算していって、最終的な答えは、
dp[T-1][0], dp[T-1][1], dp[T-1][2], ... , dp[T-1][W] の中の最大値である。
漸化式を作ろう。
i分までにj回移動したときに得られるりんごの数を求めるとき、2つの場合がありうる。
(1) i-1分までにもうj回移動をすませてi分目には移動しない。
(2) i-1分までにj-1回移動をして、i分目に移動する。
この二つの場合を計算して大きいほうがdp[i][j]になる。
よって漸化式は、
dp[i][j] = max( dp[i-1][j] + (i分目もらえるりんご), dp[i-1][j-1] + (i分目にもらえるりんご) )
ただし、(i分目にもらえるりんご)は0か1である。

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

// j回移動したあとにtree(1 or 2)が来たらりんごをゲットできるかどうか
// 奇数回移動したらtree2でゲット。偶数回移動したらtree1でゲット
int func(int j, int tree) {
  if (j % 2 == tree - 1) {
    return 1;
  } else {
    return 0;
  }
}

int main() {
  // 入力
  int T,W;
  cin >> T >> W;
  W = min(W, T); // T回より多く移動できないから
  vector<int> tree(T+1);
  for (int i = 1; i <= T; i++) {
    scanf("%d", &tree[i]);
  }
  // 動的計画法
  // dp[i][j] : i分までにj回移動したときに得られるりんごの最大数
  vector< vector<int> > dp(T+1, vector<int>(W+1));
  // j = 0
  dp[1][0] = (tree[1] == 1) ? 1 : 0;
  for (int i = 1; i < T; i++) {
    dp[i+1][0] = dp[i][0] + func(0, tree[i+1]);
    // cout << "dp " << i+1 << " 0 = " << dp[i+1][0] << endl;
  }
  // j > 0
  for (int j = 1; j <= W; j++) {
    // j回移動する場合のスタートはj分
    if (j == 1) {
      dp[1][1] = 1 - dp[1][0];
    } else {
      dp[j][j] = dp[j-1][j-1] + func(j, tree[j]);
    }
    for (int i = j; i < T; i++) {
      dp[i+1][j] = max(
        dp[i][j] + func(j, tree[i+1]),
        dp[i][j-1] + func(j, tree[i+1])
      );
    }
  }

  // dp[T-1][j]の最大値が答え
  int res = 0;
  for (int j = 0; j <= W; j++) {
    res = max(res, dp[T][j]);
  }

  // 出力
  cout << res << endl;
}

POJ3616: Milking Time

3616 -- Milking Time

問題概要

牛がN時間ミルクを出す。ジョンは搾乳可能な時間帯のリストを持っている。リストはM個の期間からなり、期間の重複があり得る。各期間iにはそれぞれ開始時間starting_our(i)、終了時間ending_hour(i)、その期間に牛から搾乳できるミルクの量efficiency(i)が与えられている。牛は搾乳期間の間ミルクを出すが、期間が終わると時間Rの休憩を入れなければならない。牛から搾乳できるミルクの最大量を求めよ。
1 <= N <= 1,000,000
1 <= M <= 1,000
0 <= starting_our(i) < ending_hour(i) <= N
1 <= efficiency(i) <= 1,000,000
1 <= R <= N
例:N=12, M=4, R=2

                        • effi

*RR 8
** 19
***RR 24
***RR 31
このとき、ミルクの最大量は19+24=43。

解法

はじめに搾乳期間のリストを開始時間の小さい順にソートする。
dp[i] = (搾乳期間i番目以降の期間から選んだときの最大ミルク量)
として漸化式を作る。dp[0]が答えになる。
dp[i]の求め方は次の2つの場合を考える。
(1) 期間iを選ばないときの最大いミルク量(dp[i-1]と等しい)
(2) 期間iを選んだときの最大ミルク量
ここで、(2)の求め方は次のようになる。
期間iの終了時間+R以降に開始時間がある期間のうち、最初のものをjとする。すると(2)の値は、
(期間iの搾乳量effi) + dp[j]
となる。
以上から漸化式は、
dp[i] = max( dp[i-1], dp[j] + (期間iのeffi) )
となる。

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
// 搾乳期間を構造体で定義
struct Interval {
  int s, e, effi; // starting_our, ending_hour+R, efficiency
  bool operator<(const Interval& another) const {
    return s < another.s;
  }
};

int main() {
  // 入力
  // ifstream cin( "test.txt" );
  int N, M, R;
  cin >> N >> M >> R;
  vector<Interval> v(M);
  for (int i = 0; i < M; i++) {
    cin >> v[i].s >> v[i].e >> v[i].effi;
    v[i].e += R;
  }
  // 開始時間の早い順にソート
  sort(v.begin(), v.end());

  // 計算
  vector<int> dp(M+1);
  int j, comp;
  dp[M] = 0;
  dp[M-1] = v[M-1].effi;
  for (int i = M-2; i >= 0; i--) {
    // 開始時間がv[i].e以降の最初の期間を検索する
    j = i+1;
    while (j < M) {
      if (v[i].e <= v[j].s) {
        break;
      }
      j++;
    }
    // 検索した値jをもとに漸化式で比較すべき値を求める
    comp = dp[j];
    // 漸化式
    dp[i] = max(dp[i+1], v[i].effi + comp);
  }

  // 出力
  cout << dp[0] << endl;
}

POJ3280: Cheapest Palindrome

3280 -- Cheapest Palindrome

問題概要

N種類のアルファベットからなる長さMの文字列が与えられる。
文字列に文字を追加したり削除したりして、回文にしたい。文字の追加も削除も任意の位置に行える。文字の追加と削除には文字の種類ごとにコストがかかる。追加と削除のコストは別に与えられる。文字列を回文にするのにかかる最小コストを求めよ。
1 <= M <= 2,000
1 <= N <= 26
0 <= cost <= 10,000

解法

POJ 3280 - Cheapest Palindrome - プログラミングコンテストの記録 を参考にした。
dp[i][j] = ( [i,j)を修正して回文にする最小コスト )
とする。
文字の追加と削除はどちらを選んでも変わらないので、最初から
cost(文字) = min( 追加コスト, 削除コスト )
としておく。
(文字数mの文字列を回文にする最小コスト) =
min(
(左1文字を除いた文字数m-1の文字列の最小コスト) + cost(左1文字),
(右1文字を除いた文字数m-1の文字列の最小コスト) + cost(右1文字),
(もし左右の文字が同じなら左右の1文字ずつを除いた文字数m-2の文字列の最小コスト)
)
である。これを頑張ってdpの漸化式にして実装する。

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
const int INF = 1000000000;

int main() {
  // ifstream cin( "test.txt" );
  // 入力
  int N, M;
  cin >> N >> M;
  char str[2000];
  cin >> str;
  int cost[26];
  char c;
  int a, d;
  for (int i = 0; i < N; i++) {
    cin >> c >> a >> d;
    cost[c - 'a'] = min(a,d);
  }
  // 動的計画法
  vector< vector<int> > dp(M, vector<int>(M+1, INF));
  for (int i = 0; i < M; i++) {
    dp[i][i]   = 0;
    dp[i][i+1] = 0;
  }
  for (int l = 2; l <= M; l++) {
    for (int i = 0; i + l <= M; i++) {
      dp[i][i+l] = min(dp[i][i+l-1] + cost[str[i+l-1] - 'a'],dp[i+1][i+l] + cost[str[i] - 'a']);
      if (str[i] == str[i+l-1]) {
        dp[i][i+l] = min(dp[i][i+l], dp[i+1][i+l-1]);
      }
    }
  }
  // 出力
  cout << dp[0][M] << endl;
}