A32397 题解（贪心+广搜）

赛时的做法，反正就是 $Ac$ 了。

---

贪心策略&证明

设有 $i \le j$，则第 $j$ 项应该选择最远的可以到达的点。
证明：由题，易得，证毕。

我没开玩笑，确实很好想到。

---

接下来套一个广搜就可以了，优先先让起点能跳到的地方入队，随后一维广搜，注意从后往前搜。

$Ac$ 代码

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int t;
int n,k;
char a[10005];
int vis[10005];
int main(){
	cin>>t;
	while(t--){
		memset(vis,0,sizeof vis);
		queue<int> q;
		int cnt=0;
		cin>>n>>k;
		cin>>a;
		if(n<=k){
			cout<<-1<<endl;
			continue;
		}
		for(int i=k;i>=0;i--){
			if(a[i]=='#'){
				q.push(i);
				vis[i]=1;
			}
		}
		while(q.size()){
			int x=q.front();
			//cout<<x<<endl;
			q.pop();
			if(x+k+1>=n){
				cnt++;
				continue;
			}
			for(int i=x+k+1;i>x;i--){
				if(a[i]=='#' && !vis[i]){
					q.push(i);
					vis[i]=1;
					break;
				}
			}
		}
		cout<<cnt<<endl;
	}
}