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 = ;
// scan input and make segments
for (int j = ; 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 = ; j <= q; j++)
for (int k = ; k <= q; k++)
b[j][k] = numeric_limits<int>::max();
for (int j = ; j <= q; j++)
b[j][j] = ;
for (int j = 1; j <= q; j++) {
for (int k = ; 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[][q] << endl;
}
}