这道题目考查的是动态规划。

我们定义状态$dp[i]$代表$1\sim i$全覆盖网络的最小花费。

那么需要分类讨论，第$i$个点是否通过WIFI覆盖。 1.不通过WIFI覆盖，那么状态转移方程就是 $dp[i]=dp[i-1]+i$。 2.通过WIFI覆盖，我们需要找到可以覆盖 $i$ 这个位置,最左边的WIFI位置(保证花费最小),也就是 $i-k$ 这个位置安装WIFI。 $i-k$ 这个位置安装WIFI覆盖的范围是$i-2k\sim i$,所以我们只需要在这个范围内找一个最小值进行转移即可(注意不要漏掉$i-2k-1$,加上$i-k$覆盖的范围，正好可以满足$1\sim i$全覆盖)。那么状态转移方程就是$$\min_{j = \max(0, i-2k-1)}^{i-1} \text{dp}[j]+i-k$$。

注意，由于我们考虑的是右端点，所以更新的答案都在右端点中。当第n个位置是1，那么我们最大会更新到n+k这个位置。所以最终的答案是$$\min_{i = n+k}^{n} \text{dp}[i]$$ ，也就是 $dp[n]$ 到 $dp[n+k]$之间的最小值。

如果使用for循环来找到区间最小值，那么时间复杂度将会达到$O((n+k)\times k)$，时间复杂度太大了，会导致超时。所以可以考虑采用单调队列、树状数组、线段树等方法来优化这一步骤，将时间复杂度降低。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
ll dp[2 * maxn];
int main()
{
	int n, k;
	cin >> n >> k;
	char s[maxn];
	scanf("%s", s + 1);
	memset(dp, 0, sizeof dp);
	deque <int> d;
	d.push_back(0);
	for (int i = 1; i <= n + k; i++) //必须考虑区间最右端的房间.
	{
		dp[i] = dp[i - 1] + i;
		if (i - k > 0 && s[i - k] == '1' )
		{
			while (!d.empty() && d.front() < i - 2 * k - 1) d.pop_front();
			dp[i] = min(dp[i], dp[d.front()] + i - k);
		}
		while (!d.empty() && dp[d.back()] >= dp[i]) d.pop_back(); //获取区间最小值。 如果dp[j] > dp[i], j < i 这说明第j个房间被后面的路由器覆盖。
		d.push_back(i);
	}
	ll m = 0x3f3f3f3f3f3f3f3f;  //最大值超过了int
	for (int i = n; i <= n + k; i++)  //   可能出现   001101   或者  001100  这两种情况，所以最优解并不一定是dp[n]但一定出现在 dp[n] 到 dp[n+k]之间的.
	{
		m = min(dp[i], m);
	}
	cout << m;
	return 0;
}