1 条题解
-
0118爱好者 (mengqingyu) LV 10 @ 2024-7-26 9:34:03
#include <stack> #include <cmath> #include <vector> #include <string.h> #include <queue> #include <stdio.h> #include <iomanip> #include <cstdio> #include <algorithm> #define int long long #define ll long long #define ls now << 1 #define rs now << 1 | 1 using namespace std; const int N = 201010; const int INF = 0x3f3f3f3f3f3f3f3f; inline int read() { int sum = 0, ff = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') { ff = -1; } c = getchar(); } while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); } return sum * ff; } int T, n, k; char s[N]; int f[N][2]; int t[N << 2]; void insert(int now, int l, int r, int x, int g) { if(l == r) { t[now] = g; return; } int mid = l + r >> 1; if(x <= mid) { insert(ls, l, mid, x, g); } else { insert(rs, mid + 1, r, x, g); } t[now] = min(t[ls], t[rs]); } int query(int now, int l, int r, int x, int y) { if(x <= l && r <= y) { return t[now]; } int mid = l + r >> 1; int res = INF; if(x <= mid) { res = min(res, query(ls, l, mid, x, y)); } if(y > mid) { res = min(res, query(rs, mid + 1, r, x, y)); } return res; } signed main() { memset(t, 0x3f, sizeof(t)); memset(f, 0x3f, sizeof(f)); f[0][0] = f[0][1] = 0; n = read(); k = read(); scanf("%s", s); for(int i = 1; i <= n; i ++) { f[i][1] = min(f[i - 1][0], f[i - 1][1]) + i; if(i > 1) { f[i][0] = query(1, 1, n, max(i - k, (ll)1), i - 1); } if(s[i - 1] == '1') { f[i][1] = min(f[i][1], f[max((ll)0, i - k - 1)][0] + i); f[i][1] = min(f[i][1], f[max((ll)0, i - k - 1)][1] + i); insert(1, 1, n, i, f[i][1]); } } cout << min(f[n][1], f[n][0]); return 0; }
- 1
信息
- ID
- 2893
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 20
- 已通过
- 2
- 上传者