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