http://community.topcoder.com/stat?c=problem_statement&pm=14789
N要素の配列がある。
各要素を隣合う要素の色が異なるように着色していく。
各色について着色された要素の最大値を取り、その総和の最小値を答えよ
前提知識
考察過程
1. 色はなるべく少ないほうが良さそう
2. しかし、2色より3色の方がいい場合もある
3. 3色で十分なのでは？という仮定
4. もう少し自明なことを探してみると「配列内の最大値は必ずある色の最大値となる」ことが分かる
5. 3色で十分だが、最大値の色は固定できる（1番目の色としよう）
6. あと2つの色の最大値が未定なので、2番目の色を決めてみる
7. 決めると、3番目の色の最大値はDPでできそう
8. 制約的にも2色目は全探索できる→OK
解説
色は3色で十分である。
2色での最小値（solve1関数）と3色での最小値（solve2関数）をそれぞれ計算して最適な方を採用しよう。
solve1関数は交互に色を決めていくだけなので、solve2関数を以下で説明する。
配列内の最大値の添字をc0とする。
この要素を1色目の最大値としよう。
2色目の最大値をどの要素にするかを全探索する。
2色目の最大値がc1番目であるとする。
最後は3色目の最大値の最小値を探すが、これをDPで解決しよう。
dp[i][c] := i番目まで色が確定していて、最後の色がcであるときの3色目の最大値の最小値
遷移が少しややこしいが、c0番目とc1番目の要素だけ処理を分けて考えよう。
DPが終わると、「X[c0] + X[c1] + dp[N][0～3]の最小値」が最終的な答えになる。
これの最小値が答えになる。
int N, X[1010]; int solve1() { int v[2] = { 0, 0 }; rep(i, 0, N) chmax(v[i % 2], X[i]); return v[0] + v[1]; } int dp[1010][4]; int solve2() { int c0 = 0; rep(i, 0, N) if (X[c0] < X[i]) c0 = i; int res = inf; rep(c1, 0, N) if (c1 != c0) { rep(i, 0, N + 1) rep(c, 0, 4) dp[i][c] = inf; dp[0][3] = 0; rep(i, 0, N) rep(c, 0, 4) { if (i == c0) { if(c != 0) chmin(dp[i + 1][0], dp[i][c]); } else if (i == c1) { if (c != 1 and X[i] <= X[c1]) chmin(dp[i + 1][1], dp[i][c]); } else { if (c != 0) chmin(dp[i + 1][0], dp[i][c]); if (c != 1 and X[i] <= X[c1]) chmin(dp[i + 1][1], dp[i][c]); if (c != 2) chmin(dp[i + 1][2], max(dp[i][c], X[i])); } } int mi = inf; rep(c, 0, 4) chmin(mi, dp[N][c]); chmin(res, X[c0] + X[c1] + mi); } return res; } struct LineColoring { int minCost(vector<int> x) { N = x.size(); rep(i, 0, N) X[i] = x[i]; return min(solve1(), solve2()); } };
