一只青蛙现在在一个数轴上，它现在要从点 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; }
