首页 > 代码库 > Codeforces Round #210 (Div. 1)——Levko and Array
Codeforces Round #210 (Div. 1)——Levko and Array
题目链接
- 题意：
n、k，表示n个点，每个点有一个值，记c = max(abs(n[i] - n[i + 1]))，要求只能将数组中的至多k个元素值改变（变成任意值），求c的最小值 - 分析：
可以二分一下c的值，求当前数组是否能改变至多k个数切c小于二分值。判断的话可以采用DP，dp[i]表示n[i]不改变时候，满足c <= 二分值时候需要改变的数字个数。 - 注意：
DP的时候，dp[i] -> dp[j]时候，如果可以转移，那么直接dp[j] = min(dp[j], dp[i] + j - i + 1)，也就是说认为i到j之间的元素都进行了改变。这个正确性可以这样解释：如果中间有一个元素刚好不需要改变，那么在DPi转移到这个元素然后再转移到j的时候，答案比直接从i再到j要优，所以这样转移是正确的。
const int maxn = 2100;
int ipt[maxn], dp[maxn];
int n, k;
int check(LL Max)
{
REP(i, n) dp[i] = i;
REP(i, n) REP(j, i)
if (abs(ipt[j] - ipt[i]) <= Max * (i - j))
dp[i] = min(dp[i], dp[j] + i - j - 1);
REP(i, n)
if (dp[i] + n - i - 1 <= k)
return true;
return false;
}
int main()
{
while (~RII(n, k))
{
REP(i, n)
RI(ipt[i]);
LL l = 0, r = 2e9, m;
while (l <= r)
{
m = (l + r) >> 1;
if (check(m))
r = m - 1;
else
l = m + 1;
}
cout << l << endl;
}
return 0;
}Codeforces Round #210 (Div. 1)——Levko and Array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。