给定一个包含 n 个元素的数组 a1, a2 ...一。如果我们定义一个函数 C = max |a(i+1)-a(i)|对于 i = 2 到 n-1。因此,我们可以为数组计算 C 值。现在的问题是,如果我们给定数组和 C 的一些值,应该更改数组中的多少个元素才能获得 C 的这个值?
这是此代码强制问题解决方案的一部分: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]
表示为了获得 C 的这个值而不需要更改的最大元素数,在 range [1, i]
中,我们不更改a[i]
。
然后检查每个j > i
,如果|a[i] - a[j]| <= (j - i) * C
,我们需要更改i和j之间的所有元素,则dp[j] = max(dp[j], dp[i] + 1
)