92 lines
2.1 KiB
C++
92 lines
2.1 KiB
C++
#include <algorithm>
|
|
#include <cmath>
|
|
#include <cstdio>
|
|
#include <cstring>
|
|
#include <iostream>
|
|
using namespace std;
|
|
typedef long long LL;
|
|
typedef long double LDB;
|
|
const int kMaxN = 310;
|
|
char s[kMaxN];
|
|
int N, M;
|
|
int Calc1(int st) {
|
|
int target[20] = {0};
|
|
for (int i = 0; i < M; i++) target[i] = (st >> i) & 1;
|
|
int cost[kMaxN][2] = {0};
|
|
int bucket_tot = N / M;
|
|
int left = N % M;
|
|
int initial_cost = 0;
|
|
for (int i = 0; i < left; i++)
|
|
initial_cost += s[bucket_tot * M + i] != target[i] ? 1 : 0;
|
|
for (int i = 0; i < bucket_tot; i++) {
|
|
for (int j = 0; j < M; j++) {
|
|
if (s[i * M + j] == target[j])
|
|
cost[i][1]++;
|
|
else
|
|
cost[i][0]++;
|
|
}
|
|
}
|
|
int dp[kMaxN][2];
|
|
memset(dp, 0x3f, sizeof(dp));
|
|
dp[bucket_tot][0] = initial_cost;
|
|
for (int i = bucket_tot - 1; i >= 0; i--) {
|
|
dp[i][0] = min(dp[i + 1][0] + cost[i][0], dp[i + 1][1] + cost[i][0] + 1);
|
|
dp[i][1] = min(dp[i + 1][0] + cost[i][1] + 1, dp[i + 1][1] + cost[i][1]);
|
|
}
|
|
return min(dp[0][0], dp[0][1]);
|
|
}
|
|
void Case1() {
|
|
int res = 0x3f3f3f3f;
|
|
for (int i = 0; i < N; i++) s[i] = s[i] - '0';
|
|
for (int st = 0; st < (1 << M); st++) res = min(res, Calc1(st));
|
|
printf("%d\n", res);
|
|
}
|
|
int Calc2(int st) {
|
|
int bucket_tot = N / M;
|
|
int cur_status = 0, status = 0;
|
|
int tot = 0;
|
|
for (int i = bucket_tot - 1; i >= 0; i--) {
|
|
int cur = (st >> i) & 1;
|
|
tot += cur;
|
|
cur_status ^= cur;
|
|
status <<= 1;
|
|
status |= cur_status;
|
|
}
|
|
int S[kMaxN];
|
|
for (int i = 0; i < N; i++) {
|
|
S[i] = s[i] - '0';
|
|
int block_id = i / M;
|
|
int hat = (status >> block_id) & 1;
|
|
S[i] ^= hat;
|
|
}
|
|
for (int i = 0; i < M; i++) {
|
|
int cnt_one = 0;
|
|
int cnt_zero = 0;
|
|
for (int j = i; j < N; j += M) {
|
|
if (S[j] == 1)
|
|
cnt_one++;
|
|
else
|
|
cnt_zero++;
|
|
}
|
|
tot += min(cnt_one, cnt_zero);
|
|
}
|
|
return tot;
|
|
}
|
|
void Case2() {
|
|
int bucket_tot = N / M;
|
|
int res = 0x3f3f3f3f;
|
|
for (int st = 0; st < (1 << bucket_tot); st++) res = min(res, Calc2(st));
|
|
printf("%d\n", res);
|
|
}
|
|
int main() {
|
|
#ifdef local
|
|
freopen("pro.in", "r", stdin);
|
|
#endif
|
|
scanf("%s%d", s, &M);
|
|
N = strlen(s);
|
|
if (M <= sqrt(N))
|
|
Case1();
|
|
else
|
|
Case2();
|
|
return 0;
|
|
} |