4

n 個の要素 a1、a2 ... an の配列が与えられます。関数 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;
}
4

1 に答える 1

1

このコードで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)

于 2014-01-10T06:26:39.923 に答える