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