gpt4 book ai didi

arrays - 算法 - 动态规划

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:01:53 24 4
gpt4 key购买 nike

给定一个包含 n 个元素的数组 a1, a2 ... an。如果我们定义一个函数 C = max |a(i+1)-a(i)|对于 i = 2 到 n-1。所以我们可以为我们的数组计算 C 的值。现在的问题是,如果我们给定数组和 C 的某个值,应该更改数组中的多少个元素才能获得 C 的这个值?

这是这个 codeforces 问题的解决方案的一部分: http://codeforces.com/contest/361/problem/D

它是使用动态规划解决的,但我不明白答案。谁能给我解释一下?这是代码。

/* x is the value of the function 
n the size of the array

*/
int Cal(LL x){
for(int i = 1; i <= n; i++)
dp[i] = 0;
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
if(abs(a[i] - a[j]) <= 1ll * (j - i) * x) {
dp[j] = max(dp[j], dp[i] + 1);
}
}
}
int ret = 0;
for(int i = 1; i <= n; i++)
ret = max(ret, dp[i] + 1);
return n - ret;
}

最佳答案

在此代码中,dp[i]表示在range [1, i] 中不需要更改的最大元素数,以获得C 的这个值, 我们不改变 a[i] .

然后检查每个 j > i , 如果 |a[i] - a[j]| <= (j - i) * C , 我们需要改变 i 和 j 之间的所有元素,然后 dp[j] = max(dp[j], dp[i] + 1 )

关于arrays - 算法 - 动态规划,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19981080/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com