一只青蛙现在在一个数轴上，它现在要从点 11 跳到点 nn ，它每次可以向右跳不超过 dd 个单位。比如，它可以从点 xx 跳到点 x+ax+a ( 1<=a<=d )(1<=a<=d) 。特别的，青蛙只能在有百合花的点上停留。保证点 11 和点 nn 之间有一些点有百合花。请输出青蛙到达点 nn 的最小跳跃次数。

输入输出格式
输入格式
输入的第一行包括两个正整数 nn 和 dd ( 2<=n<=100, 1<=d<=n-1 )(2<=n<=100,1<=d<=n−1) 。 输入的第二行是一个长度为 nn 的无空格字符串，由0和1组成，表示哪些点上有百合花（1表示有）。保证点 11 和点 nn 有百合花。

输出格式
输出青蛙的最小跳跃次数。如果它不可能到达，输出-1。

单调队列优化: O（n）

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <deque>
using namespace std;
const int maxn = 1e5 + 5;
char str[maxn];
int dp[maxn];
int main() {
	int n, d;
	cin >> n >> d;
	cin >> str + 1;
	if (str[1] == '0' || str[n] == '0') {
		cout << "-1" << endl;
		return 0;
	} 
	memset(dp, 64, sizeof(dp));
	dp[0] = dp[1] = 0;
	deque<int> q;
	q.push_back(1);
	int ins = 0;
	for (int i = 2; i <= n; i++) {
		if (str[i] == '1') {
			while (!q.empty() && q.front() < i - d) {
				q.pop_front();
			}	
			if (q.empty()) {
				ins = 1;break;
			}
			dp[i] = dp[q.front()] + 1;
			while (!q.empty() && dp[q.back()] > dp[i]) {
				q.pop_back();
			}
			q.push_back(i);
		}
	}
	if (ins) {
		cout << "-1" << endl;
	} else {
		cout << dp[n] << endl;
	}
	return 0;
}