题目链接：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