The Way to Home，一个不怎么明显的dp题。详见本文内容

题目

A. The Way to Home

限制

time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

描述

outputstandard output
A frog lives on the axis $Ox$ and needs to reach home which is in the point $n$. She starts from the point $1$. The frog can jump to the right at a distance not more than $d$. So, after she jumped from the point $x$ she can reach the point $x+a$, where $a$ is an integer from $1$ to $d$.
For each point from $1$ to $n$ is known if there is a lily flower in it. The frog can jump only in points with a lilies. Guaranteed that there are lilies in the points $1$ and $n$.
Determine the minimal number of jumps that the frog needs to reach home which is in the point $n$ from the point $1$. Consider that initially the frog is in the point $1$. If the frog can not reach home, print $-1$.

输入格式

The first line contains two integers $n$ and $d$ $(2 \le n \le 100, 1 \le d \le n-1)$ — the point, which the frog wants to reach, and the maximal length of the frog jump.
The second line contains a string $s$ of length $n$, consisting of zeros and ones. If a character of the string s equals to zero, then in the corresponding point there is no lily flower. In the other case, in the corresponding point there is a lily flower. Guaranteed that the first and the last characters of the string $s$ equal to one.

输出格式

If the frog can not reach the home, print $-1$.
In the other case, print the minimal number of jumps that the frog needs to reach the home which is in the point $n$ from the point $1$.

样本

1 2	8 4 10010101

1
2

4 2
1001

-1

1 2	8 4 11100101

1 2	12 3 101111100101

提示

In the first example the from can reach home in two jumps: the first jump from the point $1$ to the point $4$ (the length of the jump is three), and the second jump from the point $4$ to the point $8$ (the length of the jump is four).
In the second example the frog can not reach home, because to make it she need to jump on a distance three, but the maximum length of her jump equals to two.

思路

一个不怎么明显的dp题。
遍历字符串s，如果是1那么就考虑如下，假设当前是i位置，那么i位置的最小跳数是，从i-d到i-1这个区间内跳数的最小值，再加一。
所以关键就是怎么取得最小值。用优先队列，封装一个node，idx代表某个位置的下标，num代表这个位置的最小跳数，这个node的operator函数是将q队列弄成了以num排序的小顶堆。
遍历字符串的时候，如果是1，那么就先看堆顶的idx是否在i-d和i-1之间，如果不在，那么就pop，直到队列为空或者找到一个在区间内的为止。
队列为空，就直接是-1，如果找到了，那么就说明i位置能够到达，然后就更新i位置，将i位置的node加入堆中。

代码

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

int n, d;
char str[105];

struct node{
    int idx, num;
    bool operator < (const node& no) const{
        return num > no.num;
    }
};

int main(){
    while(~scanf("%d %d", &n, &d)){
        scanf("%s", str);
        priority_queue<node> q;
        q.push((node){0, 0});
        for (int i = 0; i < n; i++){
            if(str[i] == '1'){
                while(!q.empty() && q.top().idx + d < i){
                    q.pop();
                }
                if(q.empty()){
                    printf("-1\n");
                    break;
                }
                node no = q.top();
                if(i == n-1){
                    printf("%d\n", no.num+1);
                    break;
                }
                q.push((node){i, no.num + 1});
            }
        }
    }
    return 0;
}