SPOJ 3557. IOI04 Hermes


http://www.spoj.com/OI/problems/HERMES/

Brief description:

。。給定一個 [-m,m]×[-m,m] 的 Grid,要求順次訪問其中 n 個點。(只要和這個點處在同一行或同一列就判定為訪問到)
。。你從 (0, 0) 出發,只能豎直或水平移動。。最小化總路程。

Analysis:

樸素 DP: 90 分
// 設:
// fx[i][yy] 路過了前 i 個,當前坐標在 (x[i], yy) 的 xxx。。。
// fy[i][xx] 路過了前 i 個,當前坐標在 (xx, y[i]) 的 xxx。。。

//}/* .................................................................................................................................. */

const int N = int(2e4) + 9, C = 1009;

int fx[2][C*2], fy[2][C*2], x[N], y[N];
int n;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out2.txt", "w", stdout);
#endif

    REP_1_C(i, RD(n)){
        RDD(x[i], y[i]);
    }

#define fxq fx[q]
#define fxp fx[p]
#define fyq fy[q]
#define fyp fy[p]

    int p = 0, q = 1; REP(i, 2*C) fxp[i] = fyp[i] = abs(i - C);

    REP_1(i, n){
        swap(p, q); RST(fxp, fyp);
        REP(yy, 2*C) fxp[yy] = min(fxq[yy]+abs(x[i]-x[i-1]), fyq[x[i]+C] + abs(yy-C-y[i-1]));
        REP(xx, 2*C) fyp[xx] = min(fyq[xx]+abs(y[i]-y[i-1]), fxq[y[i]+C] + abs(xx-C-x[i-1]));
    }

    int res = INF; REP(i, 2*C){
        checkMin(res, min(fxp[i], fyp[i]));
    }
    OT(res);
}

複雜度 O(nc)。。。這個狀態和轉移相對直白。。容易想到。。。
。。。考慮進一步優化。。。

我們要 keep in mind 的只有一件事。。。

「 就是 dp 是可以拿數據結構緊湊地表示的。 。。。」

類似的例子有:
HDU Problem – 4703
Codeforces Round #172 Editorial


fxp[yy] = min(fxq[yy]+abs(x[i]-x[i-1]), fyq[x[i]+C] + abs(yy-C-y[i-1]));

但是我們仍然發現右邊的部分還是十分棘手。。。
需要對一個線性函數函數取 min 。。。。

以退為進!

我們對狀態進行 redesign 。。!!。。

// fx[i][yy] 路過了前 i 個,當前坐標在 (x[i], yy) 的 xxx。。。
改成。。。
// fx[i][yy] 路過了前 i 個,當前坐標在 (x[i], yy) 的 xxx。。。但不允許到 x[i] 之後從 yy 上滑動。。。。。

細心的朋友可能就要問了?這有什麼用呢?。。。。。。

考察轉移:
fx’ -> fx 。。。。
。。注意到我們不會在 x[i-1] 這條直線上走。。(因為等價於在 x[i] 上走。。。)

因此可以直接從 fxq[yy] 轉移。。看起來還是。。。
fxp[yy] = fxq[yy]+abs(x[i]-x[i-1]);

fy’ -> fx
。。注意。。。。我們的落點一定是在 (x[i], y[i-1])。。。
(否則。。假設我們的落點是 (x[i], y)。。那麼 y[i-1] -> y 的這段位移。。同樣可以放在 x[i] 上走。。。)

所以這裡就變成了

fx[y[i-1]] = min(fy'[xx] + |xx-x[i]| );

和之前的狀態設計中。。對應的這則轉移比較。。。

REP(yy, 2*C) fxp[yy] = min(fxq[yy]+abs(x[i]-x[i-1]), fyq[x[i]+C] + abs(yy-C-y[i-1]));

從影響的狀態是 O(n) 轉移是 O(1)。。
變成了影響的狀態是 O(1)。。轉移是 O(n)。。。

而新的狀態已經十分容易維護了。。。、、、

fx[y[i-1]] = min(fy'[xx] + |xx-x[i]| );

將絕對值拆開。。

fx[y[i-1]] =  min(
x[i] + min(fy'[xx]-xx) | xx <= x[i], 
min(fy'[xx]+xx) - x[i] | xx >= x[i]
);

線段樹維護即可。。 = =

Beautiful !!!

External Link:

Github Gist – http://www.spoj.com/OI/problems/HERMES/


後面一題:

貪心顯然是不對的。。考慮亂搞:
官方題解:

首先對橫線和豎線的坐標分別做鏡像翻轉,使它們的坐標分別都是單調遞增的,
並且相鄰的橫線和相鄰的豎線的距離根原始坐標的距離保持一致。這可以在線性時間內完成,
並且不影響答案。然後按照順序掃描所有直線,維護從原點出發的兩條移動路徑。
一條移動路徑儘可能往左走,一條移動路徑儘可能往右走,
但都保持最短路並且滿足規定的直線到達順序。這兩條移動路徑分別是上凸曲線和下凸曲線,
每掃描到反向不同的兩條直線時就根據交叉點更新其中一條移動路徑。
掃描到最後一條直線時就可以算出最短的移動路徑長度了。

尼瑪第一句話就看不懂。