算法 - 动态规划

Question

给定一个由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;
}

- Dreadly

---

你读过 http://codeforces.com/blog/entry/9529 吗？ - IVlad

在 if(abs(a[i] - a[j]) <= 1ll * (j - i) * x) { 中，1ll 是什么意思？ - artur grzesiak

@IVlad：没有，谢谢你提供的链接，我之前不知道 :) - Dreadly

@Artur：我猜是1（long long） - Dreadly

可能，C语言中i的计数范围是从0到n-1？ - Gangnus

Answer 1

在这段代码中，dp[i]表示为了获得C的这个值，在[1, i]范围内且不改变a[i]的情况下，不需要更改的元素的最大数量。

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

- axiom