https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0340?year=2016
前提知識
- 動的計画法 (想定解では貪欲で解けるので、必要不可欠ではない)
考察過程
1. pの上限が小さいのが気になる
2. 裏返しの操作は順番が逆になっても結果が変わらない
3. 先頭から順番に裏返し操作をしていくことにすると、後半に影響してくるのは操作し終わった最後の要素のみ
4. pの上限も少ないので、DPできる
解法
https://onlinejudge.u-aizu.ac.jp/solutions/problem/0340/review/3140080/hamayanhamayan/C++14
※ 想定解は貪欲法です
dpで解こう。
dp[idx][last] := idx番目まで処理が終わっていて、最後の要素にパンケーキがlast分残っているときのパンケーキの総裏返し回数のmin
左端の裏返しだけ1つのみで行えるので、別途DPを作る。
あとの遷移は次のパンケーキをlast2個残すというので遷移させる。
残すために必要な裏返し回数をdとすると、last≦dを満たす必要がある。
そうじゃないと、1つ前のパンケーキが必要な裏返し回数を満たさないためである。
あとは、最後に残ったパンケーキの裏返しを考慮して最小のものを取ると答え。
int N, P[5010]; int dp[5010][4]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> P[i]; rep(idx, 0, 5010) rep(last, 0, 4) dp[idx][last] = inf; rep(last, 0, P[0] + 1) dp[0][last] = P[0] - last; rep(idx, 0, N - 1) rep(last, 0, 4) { rep(last2, 0, P[idx + 1] + 1) { int d = P[idx + 1] - last2; if (d < last) continue; chmin(dp[idx + 1][last2], dp[idx][last] + d * 2); } } int ans = inf; rep(last, 0, 4) chmin(ans, dp[N - 1][last] + last); cout << ans << endl; }