二分+分别型dp，CF 360B - Levko and Array

目录
一、题目
1、题目形貌
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解

---

一、题目

1、题目形貌

   

  2、输入输出

2.1输入

   

  2.2输出

   

  3、原题链接

B - Levko and Array

---

二、解题报告

1、思路分析

最小化最大值，提示我们用二分
我们二分 c(a)，如何check？
分别型dp
界说 f(i) 为 第 i 个元素不变，前 i 个元素可以大概不变的元素数目的最大值
我们罗列上一个不变元素的下标 j
a 和 a[j] 可以大概同时不变的条件是我们可以大概通过修改 a[j + 1, i - 1] 使得 二者与相邻元素差值绝对值均不超过 二分值 x
即 abs(a - a[j]) <= (i - j) * x

2、复杂度

   时间复杂度： O(N^2logU)空间复杂度：O(N)
  
3、代码详解

1.  ​

复制代码

1. #include <bits/stdc++.h>
3. using i64 = long long;
4. using i32 = unsigned int;
5. using u64 = unsigned long long;
6. using i128 = __int128;
8. constexpr int inf32 = 1E9 + 7;
9. constexpr i64 inf64 = 1E18 + 7;
10. constexpr int P = 998'244'353;
12. void solve() {
13.         int n, k;
14.         std::cin >> n >> k;
16.         std::vector<int> a(n);
17.         for (int i = 0; i < n; ++ i)
18.                 std::cin >> a[i];
19.        
20.         std::vector<int> f(n, 1);
21.        
22.         auto check = [&](int x) -> bool {
23.                 f.assign(n, 1);       
25.                 for (int i = 0; i < n; ++ i) {
26.                         for (int j = 0; j < i; ++ j) {
27.                                 if (abs(a[i] - a[j]) <= 1LL * (i - j) * x)
28.                                         f[i] = std::max(f[i], f[j] + 1);
29.                         }
30.                 }
32.                 return *std::max_element(f.begin(), f.end()) >= n - k;
33.         };
34.        
35.         int lo = 0, hi = 2E9 + 1;
37.         while (lo < hi) {
38.                 int x = lo + (hi - lo) / 2;
39.                 if (check(x))
40.                         hi = x;
41.                 else
42.                         lo = x + 1;
43.         }
45.         std::cout << hi;
46. }
48. auto FIO = []{
49.         std::ios::sync_with_stdio(false);
50.         std::cin.tie(nullptr);
51.         std::cout.tie(nullptr);
52.         return 0;
53. }();
55. int main () {
56.         #ifdef DEBUG
57.                 freopen("in.txt", "r", stdin);
58.                 freopen("out.txt", "w", stdout);
59.         #endif
60.        
61.         int T = 1;
62.         // std::cin >> T;
63.         while (T --)
64.                 solve();
66.         return 0;
67. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。