二分+分别型dp，CF 360B - Levko and Array
目录一、题目
1、题目形貌
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目形貌
https://i-blog.csdnimg.cn/direct/08388e0cfcd54851a928c15642272d4e.png
2、输入输出
2.1输入
https://i-blog.csdnimg.cn/direct/21b10b739b0c4a5ba5f2e27cd25e6412.png
2.2输出
https://i-blog.csdnimg.cn/direct/7ad742e9d7b647a896e94543b5789cdd.png
3、原题链接
B - Levko and Array
二、解题报告
1、思路分析
最小化最大值，提示我们用二分
我们二分 c(a)，如何check？
分别型dp
界说 f(i) 为 第 i 个元素不变，前 i 个元素可以大概不变的元素数目的最大值
我们罗列上一个不变元素的下标 j
a 和 a 可以大概同时不变的条件是我们可以大概通过修改 a 使得 二者与相邻元素差值绝对值均不超过 二分值 x
即 abs(a - a) <= (i - j) * x
2、复杂度
时间复杂度： O(N^2logU)空间复杂度：O(N)
3、代码详解
#include <bits/stdc++.h>
using i64 = long long;
using i32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr int P = 998'244'353;
void solve() {
int n, k;
std::cin >> n >> k;
std::vector<int> a(n);
for (int i = 0; i < n; ++ i)
std::cin >> a;
std::vector<int> f(n, 1);
auto check = [&](int x) -> bool {
f.assign(n, 1);
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < i; ++ j) {
if (abs(a - a) <= 1LL * (i - j) * x)
f = std::max(f, f + 1);
}
}
return *std::max_element(f.begin(), f.end()) >= n - k;
};
int lo = 0, hi = 2E9 + 1;
while (lo < hi) {
int x = lo + (hi - lo) / 2;
if (check(x))
hi = x;
else
lo = x + 1;
}
std::cout << hi;
}
auto FIO = []{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
int main () {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int T = 1;
// std::cin >> T;
while (T --)
solve();
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]