https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d
前提知識
解説
https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4212545
今回の問題は一筆書きをしたときに通る回数と要求される回数との差を最小化する問題となる。
一筆書きという所と、最小化問題という所から、連結DPをしていく。
get(L,R) := A[L] + A[L+1] + ... + A[R]を累積和で用意しておこう。
dp[i][e] := i番目までを網羅した不完全なパスで、右側にe本の辺が伸びているときの、差の最小値
これを更新していこう。
遷移は以下のような感じ
// この部分は全く通らない dp[i + 1][0] = dp[i][0] + A[i]; // この部分を始点として初めて右側に2本辺を残す // （左スタート右終わりなので、ジグザグしても奇数になるので、偶数なら+1） if (A[i] % 2 == 0) chmin(dp[i + 1][1], dp[i][0] + 1); else chmin(dp[i + 1][1], dp[i][0]); // この部分を始点として初めて右側に2本辺を残す // （右スタート右終わりなので、ジグザグしても偶数になるので、奇数なら+1） if(A[i] == 0) chmin(dp[i + 1][2], dp[i][0] + 2); // ←これいらないかも else if (A[i] % 2 == 0) chmin(dp[i + 1][2], dp[i][0]); else chmin(dp[i + 1][2], dp[i][0] + 1); // 左側から伸びてる1本の辺をそのまま右側に1本の辺として伸ばす // （左スタート右終わりなので、ジグザグしても奇数になるので、偶数なら+1） if (A[i] % 2 == 0) chmin(dp[i + 1][1], dp[i][1] + 1); else chmin(dp[i + 1][1], dp[i][1]); // 左側から伸びてる2本の辺を右側に1本の辺にして伸ばす // （1本は左スタート左終わりなので、偶数。もう片方は左スタート右終わりなので、奇数。 // 足すと奇数なので、偶数なら+1） if (A[i] % 2 == 0) chmin(dp[i + 1][1], dp[i][2] + 1); else chmin(dp[i + 1][1], dp[i][2]); // 左側から伸びてる2本の辺を右側に2本の辺にして伸ばす // （どちらも左スタート右終わりなので、ジグザグしても奇数になり、足すと偶数なので、奇数なら+1） if (A[i] == 0) chmin(dp[i + 1][2], dp[i][2] + 2); else if (A[i] % 2 == 0) chmin(dp[i + 1][2], dp[i][2]); else chmin(dp[i + 1][2], dp[i][2] + 1);
これでDPが作れる。
rep(i, 1, L + 1) rep(e, 0, 3) chmin(ans, dp[i][e] + get(i, L - 1));
あとは、これで途中でやめた場合の一筆書きを集計しよう。
これで左側からのDPが作れたので、reverseして右側からのDPも同様に作ろう。
左側をdp, 右側をdp2とすると、境界線iを全探索して、dp[i][1,2] + dp[L-1-i][1,2]が候補となる。
dp[i][1,2]はmin(dp[i][1], dp[i][2])である。
これを集計すれば全パターン見たことになり、答えが得られる。
int L; ll A[201010]; //--------------------------------------------------------------------------------------------------- ll B[201010]; void init() { B[0] = A[0]; rep(i, 1, L) B[i] = B[i - 1] + A[i]; } ll get(int l, int r) { if (!(l <= r)) return 0; ll res = B[r]; if (l) res -= B[l - 1]; return res; } //--------------------------------------------------------------------------------------------------- ll ans = 0; ll dp[201010][3], dp2[201010][3]; void f() { init(); rep(i, 0, L + 1) rep(e, 0, 3) dp[i][e] = infl; dp[0][0] = 0; rep(i, 0, L) { // dp[i][0] -> dp[i+1][0], dp[i+1][1], dp[i+1][2] dp[i + 1][0] = dp[i][0] + A[i]; if (A[i] % 2 == 0) chmin(dp[i + 1][1], dp[i][0] + 1); else chmin(dp[i + 1][1], dp[i][0]); if(A[i] == 0) chmin(dp[i + 1][2], dp[i][0] + 2); else if (A[i] % 2 == 0) chmin(dp[i + 1][2], dp[i][0]); else chmin(dp[i + 1][2], dp[i][0] + 1); // dp[i][1] -> dp[i+1][1] if (A[i] % 2 == 0) chmin(dp[i + 1][1], dp[i][1] + 1); else chmin(dp[i + 1][1], dp[i][1]); // dp[i][2] -> dp[i + 1][2], dp[i + 1][1] if (A[i] % 2 == 0) chmin(dp[i + 1][1], dp[i][2] + 1); else chmin(dp[i + 1][1], dp[i][2]); if (A[i] == 0) chmin(dp[i + 1][2], dp[i][2] + 2); else if (A[i] % 2 == 0) chmin(dp[i + 1][2], dp[i][2]); else chmin(dp[i + 1][2], dp[i][2] + 1); } rep(i, 1, L + 1) rep(e, 0, 3) chmin(ans, dp[i][e] + get(i, L - 1)); //rep(i, 0, L + 1) rep(e, 0, 3) printf("dp[%d][%d] = %lld\n", i, e, dp[i][e]); } //--------------------------------------------------------------------------------------------------- ll solve() { init(); ans = get(0, L - 1); f(); reverse(A, A + L); init(); swap(dp, dp2); f(); rep(i, 1, L) chmin(ans, min(dp[i][1], dp[i][2]) + min(dp2[L - i][1], dp2[L - i][2])); return ans; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> L; rep(i, 0, L) cin >> A[i]; cout << solve() << endl; }
