某島

Brief description:

…. 略）

Analysis:

。。首先題目中的圖有一定誤導性。。在中間的任何時刻。。當前位置打開羊圈有兩邊的羊可以跑出時。。都立即打開當前位置的羊圈。。而不會出現圖中那種跳躍的情況。。。注意到初始位置固定。。。
所以狀態是。。dp[l][r][2] 表示向左走了 l 步。。向右走了 r 步。。且當前在區間 左/右 端點處時的最優值。。。
。。狀態類似 青蛙的煩惱。（參見黑書 p133。

。。轉移的時候需要中間未被訪問的部分的一段 rmq。。。因為是靜態。。所以選擇離線 ST。。去掉多餘部分。。並做一些位移。。可以一定程度上避免狀態轉移的時候不小心寫疵。。、、

const int N = 2009, LN = 14;

int ST[LN][N], dp[N][N][2];
int A[N], n, k, nn;

inline int rmq(int l, int r){
    r=nn-r; int lv = lg2(r-l);
    return max(ST[lv][l], ST[lv][r-(1<<lv)]);
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    while (~scanf("%d%d", &n, &k)){

        int s = 0; REP(i, n) s += RD(A[i]); nn = n-(2*k+1); ++k;

        REP(i, nn) ST[0][i] = A[k+i];

        for ( int lv = 1 ; _1(lv) < nn ; lv ++ ){
            for ( int i = 0 ; i + _1(lv)  <= nn ; i ++ )
                ST[lv][i] = max(ST[lv-1][i], ST[lv-1][i + _1(lv-1)]);
        }

        FLC(dp, 0x3f), dp[0][0][0] = dp[0][0][1] = 0;

        FOR_1(len, 1, nn) FOR_1(l, 0, len){
            int r = len - l;
            if (l) dp[l][r][0] = min(dp[l-1][r][0] + rmq(l-1, r), dp[l-1][r][1] + len * rmq(l-1, r));
            if (r) dp[l][r][1] = min(dp[l][r-1][1] + rmq(l, r-1), dp[l][r-1][0] + len * rmq(l, r-1));
        }

        int f = INF; FOR_1(l, 0, nn){
            int r = nn - l;
            REP(t, 2) checkMin(f, dp[l][r][t]);
        }

        OT(s + f);
    }
}

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1555178

Posted by xiaodao
Category: HDU