Round 1C の C を C++で書いてみた(Google Code Jam 2009)

haskellで書いたら遅かったので，C++で書いてみた．
アルゴリズムはほぼ同じ．メモ化再帰ではなく，配列でビルドアップ．

実は numeric_limits::max() で intの最大値がとりだせるらしい．

#include<iostream>
#include<cmath>
#include<limits>

using namespace std;

int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int p, q;
    cin >> p >> q;
    int s[q+1], pre = 0;

    // scan input and make segments
    for (int j = 0; j < q; j++) {
      cin >> s[j];
      s[j] -= pre + 1;
      pre = s[j] + pre + 1;
    }
    s[q] = p - pre;

    // build DP-table

    int b[q+1][q+1];
    for (int j = 0; j <= q; j++)
      for (int k = 0; k <= q; k++)
	b[j][k] = numeric_limits<int>::max();
    for (int j = 0; j <= q; j++)
      b[j][j] = 0;

    for (int j = 1; j <= q; j++) {
      for (int k = 0; j + k <= q; k++) {
	int b0 = j-1;
	for (int l = k; l <= j+k; l++)
	  b0 += s[l];
	for (int l = k; l <  j+k; l++)
	  b[k][j+k] = min(b[k][j+k], b0 + b[k][l] + b[l+1][j+k]);
      }
    }

    cout << "Case #" << i << ": " << b[0][q] << endl;
  }
}