1819번: 불끄기

https://www.acmicpc.net/problem/1819


$O((l^2+t)2^t)$

dp를 통해 (여태 본 비트 길이, 최근 t-1개의 비트) 마다 최소 1의 개수를 구해 놓는다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int dp[51][1 << 6], l, t, m, b, c[1 << 7], a[51];
vector<int> v[51][1 << 6];
int main() {
    scanf("%d%d", &l, &t);
    for (int i = 1; i <= l; i++) scanf("%1d", a + i);
    for (int i = 0, x; i < t; i++) {
        scanf("%1d", &x);
        m = m * 2 + x;
        b = b * 2 + a[i];
    }
    for (int i = 1 << t; i--;)
        for (int j = i; j; j &= j - 1) c[i]++;
    fill(&dp[0][0], &dp[50][1 << 6], 1e9);
    dp[t - 1][b] = c[b];
    for (int i = t - 1; i < l; i++) {
        for (int j = 1 << t - 1; j--;) {
            int p = (j * 2 + a[i + 1] ^ m) % (1 << t - 1);
            if (dp[i + 1][p]>dp[i][j] - c[j] + c[j * 2 + a[i + 1] ^ m]) {
                dp[i + 1][p] = dp[i][j] - c[j] + c[j * 2 + a[i + 1] ^ m];
                v[i + 1][p] = v[i][j];
                v[i + 1][p].push_back(i - t + 2);
            }
            p = (j * 2 + a[i + 1]) % (1 << t - 1);
            if (dp[i + 1][p]>dp[i][j] - c[j] + c[j * 2 + a[i + 1]]) {
                dp[i + 1][p] = dp[i][j] - c[j] + c[j * 2 + a[i + 1]];
                v[i + 1][p] = v[i][j];
            }
        }
    }
    int r = min_element(dp[l], dp[l] + (1 << t - 1)) - dp[l];
    printf("%d", v[l][r].size());
    for (auto it : v[l][r]) printf("\n%d", it);
    return 0;
}