一年一度的比賽，就算再忙也要抽點時間出來比賽…
Easy:
給定了一個只帶o或x的隊列$A$，和兩個最被是空的隊列$B$和$C$，你可以進行如下四種操作﹕
1) B.enqueue(A.dequeue);
2) C.enqueue(A.dequeue);
3) A.enqueue(B.dequeue);
4) A.enqueue(C.dequeue);
問最少進行多少操作可以把$A$的內容變成指定的狀態？
不難發現一件事﹕在答案裡，$A$的最長後綴是最終狀態的前綴。剩下來的符號要怎樣處理？留意到為甚麼有兩條隊列嗎？這是因為你可以把非後綴的字元按o或x分別放到$B$和$C$，當剩下最長後綴時則按餘下的字元從$B$或$C$取出字元。那麼一個字元對應一出一入就是兩次操作，已是最少的了。
Medium:
給了一個$N$格的地圖，每格給出$p_i$，是為第$i$格變成泥濘的路的概率。保証第一格及第$N$格不會變成泥路。現在你可以向前一步或跳過一步。給定任何一整段路的狀態，你總是選定一個走法，使得跳進泥路的數量為最少。假設你現在站在第一格，到達第$N$格的時候，平均要走進多少個泥路？
其實又不是很難動態規劃，不過我卻想了很多不確定的東西。
關鍵的觀察是﹕如果你站在一個沒有泥的路，而前方有剛好$k$個泥路，那麼你最少可以踏過$\lfloor\frac{k}{2}\rfloor$個泥路。根據這個觀察可以這樣定義狀態函數$f(i, j, k)$，其中$i$是代表位置，$j$代表當前是第幾個連續的泥路，$k$是代表總共最少走過多少個泥路。那麼$f$即為該狀態的概率。其轉移方程則是﹕
\[ f(i+1, j+1, k+\delta) := f(i+1, j+1, k+\delta) + f(i, j, k) \times p_{i+1},\text{ where }\delta = \begin{cases}1 & \text{ if $j+1 \equiv 0 \pmod{2}$ } \\ 0 & \text{ otherwise}\end{cases}\]
\[ f(i+1, 0, k) := f(i+1, 0, k) + f(i, j, k) \times (1-p_{i+1})\]
而且$f(0, 0, 0) = 1$。那麼$O(N^3)$時間可以求出所有狀態，答案則是$\displaystyle\sum_{k=0}^N f(N-1, 0, k) \cdot k$。
注意本題有很簡單的$O(N)$的動態規劃。
