DP problemset#1
用 $f[i][s][t]$ 表示考慮至第 $i$ 個選項，当前第一關經驗為 $s$，第二關經驗為 $t$ 的最小時間。但由於一旦 $s$ 超過 $s_1$ 將不能使用 $x_i,t_i$，則需枚舉最後的數，變為 $O(n^4)$，不可取。註意到，當某個 $x_i$ 加入使 $s\geq s_1$ 時，一定可以重調 $x$ 的順序使最大的 $x_{i’}$ 放到最後，所以祗需將 $x_i$ 從小至大排好序而後再 dp 即可考慮到所有情況。
複雜度：$O(n^3)$。
為防 pta 搞事，簡述下題意。$s$ 的一個子序列 $s’$ 若合法，則 $\vert LCS(s’,t)\vert\leq 1$，最小化 $s’$ 的長度，輸出此長。$\vert s\vert,\vert t\vert\leq 10^5$。
由於最長公共子序列長度不能超過 $1$，故對於 $t[i],t[j]$ 滿足 $j<i$ 則 $t[i]t[j]$ 不能做為子序列出現在 $s’$ 中。故依此根据 $t$ 建一張有向圖，每個結點表示字符集中的一個字符，且若 $u\rightarrow v$，則表示 $u$ 后能接 $v$。可以發現除掉自環後遮是一個有向無環圖。此時考慮狀態 $f[i][c]$ 表示當前考慮到 $s[i]$，有向圖中的 $c$ 字符的最大公共子序列，利用類似於序列最大子序列的求解方法求解，但注意到 $c$ 的前繼結點個數是 $O(\vert\Sigma\vert)$ 的，故複雜度為 $O(n\vert\Sigma\vert^2)$，會時間超限。換一個角度想，遮個有向圖可以理解為一個 DFA，每輸入一個字符可以使某些狀態發生轉移，且其等價類為末尾字符相同的序列，而本題祗要求長度最大的，故祗保留最大的就行了。即用 $f[i][c]$ 表示當前考慮到 $s[i]$，以 $c$ 結尾的最長合法子序列的長度即可。
複雜度：$O(n\vert\Sigma\vert)$。
每次操作相當於删去兩個數，考慮狀態 $f[i][k]$ 為考慮到第 $i$ 個點，至多删了 $k$ 個數的最大平方和。答案為 $f[n][2,4,\ldots,2n]$。
複雜度：$O(n^3)$。
很容易想用樹形 dp 解決，但狀態如何表示更為合適？若用 $f[root]$ 表示根节點开始占領整棵樹的答案，發現 $f[u] (u\neq root)$ 時與此有所不同，因為 $u$ 上没有士兵。所以理論上需有狀態 $f[u][i]$ 用於表示 $u$ 上有 $i$ 个士兵進行該樹占領的最少時間，但遮樣難免 TLE。注意到遮樣一件事，如果一子樹里有過兩個士兵及以上，則没必要擴散到其外的結点，遮是因為當某個士兵至某個深度為 $d_1$ 的結点 $v_1$ 時，此時樹上還有深度為 $d_2$ 的結點 $v_2$ 是通過新派的士兵完成占領的，那么有：
\[dep(v_1)-dep(lca(v_1,v_2))\geq dep(lca(v_1,v_2))-dep(root)\]而 $dep(lca(v_1,v_2))\geq dep(u)$，故士兵不出必此子樹。所以 $i\leq 1$ 即可，且 $u$ 上至少有過一個士兵，故 $f[u]$ 表示 $u$ 上有一個士兵時，占領此樹的最短時間。轉移考慮每個子結點 $v$ 是否將其中的士兵回溯，還是從根結點重調一個士兵，遮需要深度比較，可以發現 $v$ 中可回溯的士兵必在深度最深的位置。需注意最後一個处理的 $v$ 是可不回溯的，故可長鏈剖分，但是其實轉移時最後扣掉最大的貢獻就行了。
複雜度：$O(\sum n)$。
可以發現就是有的測試會使一些點達到最後期的狀態，所以使用 $f[S]$ 來表示當前達到了狀態 $S$ 需要的最少測試點數。由於狀態一旦滿足便一不可撤銷，故無需考慮重復。對於新加一個測試點，已經是 WA 等的狀態不再有影響，其余對用時即時耗進行更新，且不能超過最後的最大值。簡單 DP 為 $O(nm2^{3m})$，會 TLE。考慮兩種情況：
- 若最後為 WA 等的程序，達到 WA 時間空間卻未達期望，不會有貢獻；
- 對當前狀態，若最後為 WA 的還未達 WA，則時間空間超限均不行，其它非 OK 狀態亦不可，可提前處理判斷。
複雜度：$O((n+m)2^{3m})$。
注意到不可能轉圈，DP 頭至尾的 $f[i][j]$ 表示最後在 $i$，用了 $j$ 次按鈕的最大得分，以及由尾至頭的 $g[i][j]$。接著考慮哪一邊被走過兩次，之後能操作的次數就固定了，遮時兩邊分別枚舉用了幾次即可。
複雜度：$O(nm^2+n^2m)$。