Codeforces 750E 线段树DP

布满荆棘的人生 2023-08-17 17:22 232阅读 0赞

题意:给你一个字符串,有两种操作:1:把某个位置的字符改变。2:询问l到r的子串最少需要删除多少个字符,使得这个子串含有2017子序列,并且没有2016子序列?

思路:线段树上DP,我们设状态0, 1, 2, 3, 4分别为: null, 2, 20, 201, 2017的最小花费,我们用线段树来维互状态转移的花费矩阵,合并相邻的两个子串的时候直接转移即可。

代码:

  1. #include <bits/stdc++.h>
  2. #define INF 0x3f3f3f3f
  3. #define ls (o << 1)
  4. #define rs (o << 1 | 1)
  5. using namespace std;
  6. const int maxn = 200010;
  7. int a[maxn];
  8. char s[maxn];
  9. struct node {
  10. int f[5][5];
  11. void init(int x) {
  12. for (int i = 0; i < 5; i++) {
  13. for (int j = 0; j < 5; j++) {
  14. if(i == j) continue;
  15. f[i][j] = INF;
  16. }
  17. }
  18. if(x == 2) {
  19. f[0][0] = 1, f[0][1] = 0;
  20. } else if (x == 0) {
  21. f[1][1] = 1, f[1][2] = 0;
  22. } else if (x == 1) {
  23. f[2][2] = 1, f[2][3] = 0;
  24. } else if (x == 7) {
  25. f[3][3] = 1, f[3][4] = 0;
  26. } else if (x == 6) {
  27. f[3][3] = 1;
  28. f[4][4] = 1;
  29. } else if (x == -1){
  30. for (int i = 0; i < 5; i++)
  31. f[i][i] = INF;
  32. } else {
  33. for (int i = 0; i < 5; i++)
  34. f[i][i] = 0;
  35. }
  36. }
  37. void print() {
  38. for (int i = 0; i < 5; i++) {
  39. for (int j = 0; j < 5; j++) {
  40. if(f[i][j] == INF) printf("inf ");
  41. else printf("%d ", f[i][j]);
  42. }
  43. printf("\n");
  44. }
  45. }
  46. };
  47. node tr[maxn * 4];
  48. node merge(node t1, node t2) {
  49. node ans;
  50. ans.init(-1);
  51. // ans.init(-1);
  52. // printf("ans\n");
  53. // ans.print();
  54. // printf("t1\n");
  55. // t1.print();
  56. // printf("t2\n");
  57. // t2.print();
  58. for (int i = 0; i < 5; i++) {
  59. for (int j = i; j < 5; j++) {
  60. for (int k = i; k <= j; k++) {
  61. ans.f[i][j] = min(ans.f[i][j], t1.f[i][k] + t2.f[k][j]);
  62. }
  63. }
  64. }
  65. // printf("ans\n");
  66. // ans.print();
  67. return ans;
  68. }
  69. void build(int o, int l, int r) {
  70. if(l == r) {
  71. tr[o].init(a[l]);
  72. return;
  73. }
  74. int mid = (l + r) >> 1;
  75. build(ls, l, mid);
  76. build(rs, mid + 1, r);
  77. tr[o] = merge(tr[ls], tr[rs]);
  78. }
  79. void update(int o, int l, int r, int ql, int qr, int val) {
  80. if(l == r) {
  81. tr[o].init(val);
  82. return;
  83. }
  84. int mid = (l + r) >> 1;
  85. if(ql <= mid) update(ls, l, mid, ql, qr, val);
  86. if(qr > mid) update(rs, mid + 1, r, ql, qr, val);
  87. tr[o] = merge(tr[ls], tr[rs]);
  88. }
  89. node query(int o, int l, int r, int ql, int qr) {
  90. if(l >= ql && r <= qr) {
  91. return tr[o];
  92. }
  93. int mid = (l + r) >> 1;
  94. node ans;
  95. ans.init(-1);
  96. if(ql <= mid && qr > mid) ans = merge(query(ls, l, mid, ql, qr), query(rs, mid + 1, r, ql, qr));
  97. else if(ql <= mid) ans = query(ls, l, mid, ql, qr);
  98. else if(qr > mid) ans = query(rs, mid + 1, r, ql, qr);
  99. return ans;
  100. }
  101. int main() {
  102. int n, m, l, r;
  103. scanf("%d%d", &n, &m);
  104. scanf("%s", s + 1);
  105. for (int i = 1; i <= n; i++) {
  106. a[i] = s[i] - '0';
  107. }
  108. build(1, 1, n);
  109. for (int i = 1; i <= m; i++) {
  110. scanf("%d%d", &l, &r);
  111. node ans = query(1, 1, n, l, r);
  112. if(ans.f[0][4] == INF) printf("-1\n");
  113. else printf("%d\n", ans.f[0][4]);
  114. }
  115. }

  

转载于:https://www.cnblogs.com/pkgunboat/p/11488340.html

发表评论

表情:
评论列表 (有 0 条评论,232人围观)

还没有评论,来说两句吧...

相关阅读

    相关 Codeforces 750E 线段DP

    题意:给你一个字符串,有两种操作:1:把某个位置的字符改变。2:询问l到r的子串最少需要删除多少个字符,使得这个子串含有2017子序列,并且没有2016子序列? 思路:线段树

    相关 Codeforces 735E 树形DP

    题意:给你一棵树,你需要在这棵树上选择一些点染成黑色,要求染色之后树中任意节点到离它最近的黑色节点的距离不超过m,问满足这种条件的染色方案有多少种? 思路:设dp\[x\]\

    相关 Codeforces 722E 组合数学 DP

    题意:有一个n \ m的棋盘,你初始在点(1, 1),你需要去点(n, m)。你初始有s分,在这个棋盘上有k个点,经过一次这个点分数就会变为s / 2(向上取整),问从起点到终