時間安排

7:40–7:50 讀題，T1 貌似是簽到，T2,T4 DP,T3看起來很不可做。
7:50–8:00 T1,差分一下然后模擬就行了。
8:00–10:20 T2,注意到值域很小，可以考慮狀壓，想到一個狀壓狀態(tài)數(shù)較少的 dp ，然后掛得徹底。發(fā)現(xiàn)有一些情況沒考慮到，那就不得不增加狀態(tài)維度，可這樣的話狀態(tài)數(shù)就非常大。想了好久沒有想到什么更小的表示，于是就硬著頭皮寫了?？梢阅玫?70 分左右。
10:20–12:00 T4,考慮怎么 dp ，為了不重，那么就要盡可能少的操作，問題在于對于一個狀態(tài)我壓根不知道最少的操作是什么。分討一下發(fā)現(xiàn)情況非常復雜，不知道怎么 dp 。寫了個dfs 暴力。

回顧反思

T2:
基本思路和正解差不多，不過賽時做法復雜度較劣，主要有兩點。
一是 dp 轉(zhuǎn)移設計上，題目要求劃分為若干個子段，于是我每次都要枚舉最后一段的左端點。但實際上一段的信息非常好維護，于是可以考慮直接在 dp 狀態(tài)里加入當前未結(jié)束的段的信息，對于一個新元素考慮是另起一段還是加入當前段就行了。
二是狀壓狀態(tài)數(shù)上，直接暴力枚舉狀壓的狀態(tài)復雜度很大，但是顯然很不滿，通過 bfs 處理出有用的狀態(tài)，發(fā)現(xiàn)只有 100 多個非常少，于是復雜度就對了。
對于這種一段的信息非常簡單的可以考慮在 dp 時直接維護當前未結(jié)束段的信息。
狀壓的狀態(tài)數(shù)很大時，一定要想想是不是每個狀態(tài)都真的有用，去 bfs/dfs 一下會發(fā)現(xiàn)有用的狀態(tài)往往很少。
T3:
貌似很高深。
T4:
比賽的時候壓根不知道從何下手設計 dp 。是否必要操作，操作的先后沒法確定等一系列問題。
由于本題操作的一些優(yōu)秀性質(zhì)，發(fā)現(xiàn)對于一個結(jié)束態(tài)，有些區(qū)間如果要操作必然是最后幾次操作，將其去掉后剩下的也能如此劃分。于是劃分出若干個塊，每個塊若要操作與相鄰的塊有一定依賴關(guān)系，于是就有了操作的先后關(guān)系，枚舉相鄰的幾個塊是否操作了，根據(jù)分討依賴關(guān)系就可以得到當前塊操作是否是必要的。
已知操作后的最終序列，考慮將操作序列映射到原序列。比如本題可以先把對應操作區(qū)間劃分出來，討論區(qū)間之間的依賴關(guān)系。