fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define file(name) if (fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
  5. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  6. template <typename T1, typename T2> bool mini(T1 &a, T2 b) {if (a > b) a = b; else return 0; return 1;}
  7. template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {if (a < b) a = b; else return 0; return 1;}
  8. const int inf = 2e9 + 7;
  9. const int mod = 1e9 + 7;
  10. const int N = 4e5 + 5;
  11.  
  12. int n, m, k, a[N], minn[N];
  13.  
  14. signed main() {
  15. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  16. file("");
  17.  
  18. // Cải tiến dp bằng nhận xét
  19. // Nhận xét: min chỉ có thể thay đổi khi mà xuất hiện thêm cây hỏng khác
  20. // Theo trực quan, ta cũng nên bắt đầu bao từ cái cây hỏng để maximise được cái lượng cây hỏng quét qua (minimise được cái lượng cây không hỏng được bao)
  21. // Chứng minh:
  22. // 1) Khi bao quanh x cái cây hỏng mà chuyển qua 1 ô kề bên thì thành x => vẫn chỉ bao quanh k - x cây không hỏng
  23.  
  24. // 2) Khi bao quanh x cái cây hỏng mà chuyển qua 1 ô kề bên thì thành x + 1 cây hỏng (+1 cây hỏng ở biên phải)
  25. // Khi này đoạn được xét sẽ -1 cây không hỏng được bao và còn lại y nguyên => +1 cây hỏng => có lợi
  26.  
  27. // 3) Khi mà đang bao x cái cây hỏng mà chuyển qua 1 ô kề bên thì thành x - 1 cây hỏng (-1 cây hỏng ở biên trái)
  28. // Khi này: đoạn đang bao quanh thì sẽ + 1 cây không hỏng, tổng các đoạn trước đó trừ nhiều nhất 1 cây không hỏng (do có thêm sự xuất hiện của 1 cây hỏng chưa được bao) / hoặc trường hợp tệ hơn là sẽ + >= 0 cây không hỏng nữa
  29. // + 1 - 1 = 0 => trường hợp tốt nhất là không thay đổi
  30. // => Ta chỉ cần dp ở các điểm mà có cây hỏng.
  31.  
  32. // 4) Thêm một điều lưu ý nữa là khi chọn điểm ở ngoài biên thì min cũng có thể thay đổi
  33. // Cụ thể là sẽ thay đổi ở các điểm mà a[i] + k - 1 > n (bao từ a[i] và kéo dài ra k ô)
  34. //Có thể hiểu đơn giản về việc tại sao lại không chọn a[m] + k - 1 mà lại chọn tập các điểm i là vì
  35. //Ta có thể dùng cái biên đó để bao nhiều điểm một cách tối ưu thay vì chỉ có bao được 1 điểm duy nhất (hoang phí)
  36. //Nếu mà chỉ bao 1 điểm và chừa ra 1 đống điểm ở giữa đó thì có khi việc bao bình thường sẽ tốn kém hơn rất nhiều, do vẫn đụng phải các cây không hỏng
  37. //Do đó ta có thể tiết kiệm hơn bằng việc dùng cái bao ở ngoài biên đó bao nhiều cây hỏng ở trong
  38. //Tương tự với cái ngoài biên bên trái (thực ra tui cũng có làm vậy mà tui không nhận ra do tui dùng max(0, ...))
  39.  
  40. // code DP (sub 2)
  41. // cin >> n >> k >> m;
  42. // for (int i = 1; i <= m; i++) {
  43. // int x; cin >> x;
  44. // a[x] = true;
  45. // }
  46. // for (int i = 1; i <= n + k; i++) sum[i] = sum[i - 1] + a[i];
  47. // memset(minn, 0x3f, sizeof(minn));
  48. // minn[0] = 0;
  49. // for (int i = 1; i <= n + k; i++) {
  50. // f[i] = minn[max(0, i - k)] + min(n, i) - max(1, min(n, i - k + 1)) + 1 - (sum[i] - sum[max(0, i - k)]);
  51. // if (a[i]) minn[i] = f[i];
  52. // else minn[i] = min(minn[i - 1], f[i]);
  53. // }
  54.  
  55. // for (int i = 1; i <= n + k; i++) cerr << minn[i] << " ";
  56. // cout << n - m - minn[n + k];
  57.  
  58. //sub 3
  59. cin >> n >> k >> m;
  60. int original_m = m;
  61. for (int i = 1; i <= m; i++) cin >> a[i];
  62. sort(a + 1, a + 1 + m);
  63. for (int i = 1; i <= original_m; i++) if (a[i] + k - 1 > n) {
  64. a[m + 1] = a[i] + k - 1;
  65. m++;
  66. }
  67. memset(minn, 0x3f, sizeof(minn));
  68. minn[0] = 0;
  69. for (int i = 1; i <= m; i++) {
  70. int x = max(0, int(upper_bound(a + 1, a + 1 + m, a[i] - k) - a - 1)); //ở vị trí a[i] - k đã bao được bao nhiêu cây không hỏng
  71. minn[i] = minn[x] + min(n, a[i]) - max(1, min(n, a[i] - k + 1)) + 1 - (min(original_m, i) - x);
  72. if (i > original_m) mini(minn[i], minn[i - 1]);
  73. }
  74.  
  75. cout << n - original_m - minn[m];
  76. cerr << "Time elapsed: " << TIME << "s.\n";
  77. return 0;
  78. }
Success #stdin #stdout #stderr 0.01s 5320KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
Time elapsed: 0.007317s.