問題
https://codeforces.com/contest/1353/problem/E (新しいタブで開く)
問題文
個のランプがあり、 が 0
ならランプ は消灯、 1
ならランプ は点灯している。
整数 も与えられる。
1 回の操作で、1 つのランプを選んで、状態を反転させることができる。
-periodic とは、それぞれ ON の状態のランプがちょうど 個離れているような状態のことである。例えば、100100100
は -periodic である。
-periodic にするために必要な操作の回数の最小値は?
制約
- の総和は を超えない
サンプル
6 9 2 010001010 9 3 111100000 7 4 1111111 10 3 1001110101 1 1 1 1 1 0
1 2 5 4 0 0
考察
DP した。
具体的には、「dp[i] = 番目が ON のとき、それより前のランプを最小でいくつ変える必要があるか」をまず考える。
その後 番目が一番左にある場合とそうでない場合で最小値をとる。
全部調べたら、 番目が一番右にあることを考えて、加える。
最終的には「dp[i] = 番目が ON で一番右にあるときに最小でいくつ変える必要があるか」になってる。
これの最小値を出力する。
毎回「いくつ変えるべきか?」を数えると間に合わないので、累積和を使う。
また、コーナーケースで全部 OFF の場合があるので注意。
コード
https://codeforces.com/contest/1353/submission/127026730 (新しいタブで開く)
void solve() { int n, k; cin >> n >> k; string s; cin >> s; vector<int> sum(n + 1, 0); rep(i, n) { sum[i + 1] = sum[i] + (s[i] - '0'); } vector<int> dp(n, 1e9); dp[0] = 0; rep(i, n) { int f = sum[i] - (s[i] - '1'); int g = 1e9; if (i - k >= 0) { g = dp[i - k] + (sum[i] - sum[i - k + 1]) - (s[i] - '1'); } dp[i] = min(f, g); } rep(i, n) { dp[i] = dp[i] + sum[n] - sum[i + 1]; } dp.push_back(sum[n] - sum[0]); cout << *min_element(dp.begin(), dp.end()) << endl; }