题目链接：https://codeforces.com/problemset/problem/1216/F
题目大意：有n个房间，1代表这个房间可以安装路由器(代价为这个房间的编号i)，且路由器覆盖范围为左侧到max(1, i - k), 右侧到max(n, i + k)；0代表这个房间不能安装路由器，需要直接连接上网(代价为这个房间的编号i)，或者可以蹭安装了路由器房间的网(没有代价)。问让这n个房间能全部连上网的最小代价是多少。
用线段树维护的dp
设dp[i][0/1]表示前i - 1个位置已经完成了覆盖，第i个位置 不放(0)/放(1) 路由器时，所需花费的最小代价。
考虑状态转移如下：
假设前i - 1个房间已经用最小代价全部连接上网，
- 无论这个房间是属性是0还是1，都有：dp[i][0] = min{dp[i - 1][0] + i, query(前面放路由器, 1, 1, n, i - k, i - 1)};
这表示，第i号房间不放路由器的话，前i个房间全部连接上网的代价 = min{前i - 1个房间全部连接上网的最小代价 + 第i个房间直接连接上网的代价i, 蹭前面放置路由器房间的网(此时第i个房间没有花费任何代价,转移到这的时候代价会和它前面放路由器房间的代价相同)}
2. 对于可以放置路由器的房间，有：dp[i][1] = min{query(前面放路由器, 1, 1, n, i - k, i - 1), query(前面不放路由器, 1, 1, b, i - k - 1, i - 1)} + i;
这表示，第i个房间选择放路由器的话，前i个房间全部连接上网所需要的最小代价 = min{[i - K - 1, i - 1]区间内的使用路由器的最小值, 前面的[i - K, i - 1]区间的不使用路由器的最小值} + 这个房间放置路由器的代价i
1 #include<iostream>
2 #include<vector>
3 #include<map>
4 #include<algorithm>
5 #include<queue>
6 #include<cstdio>
7 #include<cmath>
8 #include<string>
9 #include<set>
10 #include<complex>
11 #include<cstdio>
12 #include<cstring>
13 #include<stack>
14 #include<iomanip>
15 #include<bitset>
16 #include<typeinfo>
17 #include<random>
18 #include<unordered_map>
19 #include<unordered_set>
20 using namespace std;
21
22 const int maxn = 2e5 + 10;
23 const long long inf = 0x3f3f3f3f3f3f3f3f;
24
25 int n, k;
26 char str[maxn];
27 long long dp[maxn][5];
28
29 long long tree_no[maxn * 4];
30 long long tree_yes[maxn * 4];
31
32 void push_up(long long tmp[], int rt){
33 int ls = rt * 2, rs = rt * 2 + 1;
34 tmp[rt] = min(tmp[ls], tmp[rs]);
35 }
36
37 void build(long long tmp[], int rt, int l, int r){
38 tmp[rt] = inf;
39 if(l == r){
40 return;
41 }
42 int mid = (l + r) / 2;
43 build(tmp, rt * 2, l, mid);
44 build(tmp, rt * 2 + 1, mid + 1, r);
45 // push_up(tmp, rt);
46 }
47
48 long long query(long long tmp[], int rt, int l, int r, int ql, int qr){
49 if(ql <= l && r <= qr) return tmp[rt];
50 int mid = (l + r) / 2;
51 if(qr <= mid) return query(tmp, rt * 2, l, mid, ql, qr);
52 else if(ql > mid) return query(tmp, rt * 2 + 1, mid + 1, r, ql, qr);
53 else{
54 long long ans_ls = query(tmp, rt * 2, l, mid, ql, qr);
55 long long ans_rs = query(tmp, rt * 2 + 1, mid + 1, r, ql, qr);
56 return min(ans_ls, ans_rs);
57 }
58 }
59
60 void update(long long tmp[], int rt, int l, int r, int p, long long x){
61 if(l == r){
62 tmp[rt] = x;
63 return;
64 }
65 int mid = (l + r) / 2;
66 if(p <= mid) update(tmp, rt * 2, l, mid, p, x);
67 else update(tmp, rt * 2 + 1, mid + 1, r, p, x);
68 push_up(tmp, rt);
69 }
70
71 int main(){
72 scanf("%d %d", &n, &k);
73 scanf("%s", str + 1);
74 build(tree_no, 1, 1, n);
75 build(tree_yes, 1, 1, n);
76 dp[n][1] = inf; dp[0][0] = 0;
77 for(int i = 1; i <= n; i++){
78 if(i > 1) dp[i][0] = min(dp[i - 1][0] + i, query(tree_yes, 1, 1, n, i - k, i - 1));
79 else dp[i][0] = i;
80 update(tree_no, 1, 1, n, i, dp[i][0]);
81 if(str[i] == '1'){
82 if(i - k <= 1) dp[i][1] = i;
83 else if(i > 1) dp[i][1] = min(query(tree_yes, 1, 1, n, i - k, i - 1),
84 query(tree_no, 1, 1, n, i - k - 1, i - 1)) + i;
85 update(tree_yes, 1, 1, n, i, dp[i][1]);
86 }
87 }
88 printf("%lld\n", min(dp[n][1], dp[n][0]));
89 return 0;
90 }参考博客：https://blog.csdn.net/qq_41730082/article/details/101119577