1 条题解

  • 0
    #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
    上传者