Mato is No.1

i    ：  0   1   2   3   4
D[i]：  2   4   3   2   \
M[i]： 1   2   6  14   \
S[i]：  0  3   7  10  16
可以發現，D[0]值減小1之后，S[1..3]的值都減小了1，而S[4]的值不變。這是因為在D[0]減小1之前，對于1<=i<3均有S[i]>M[i]，D[0]若減小1，顯然S[1]會減小1，而由于S[1]>M[1]，S[1]=max{S[1], M[1]}，所以S[1]的值減小1會使得max{S[1], M[1]}減小1，從而S[2]的值減小1，然后由于初始的S[2]>M[2]，同樣會使得S[3]減小1，而初始的S[3]<=M[3]，故S[3]減小1不會使得max{S[3], M[3]}發生變化，所以S[4]的值不會受到影響。
所以，可以得到：D[i]減小1，會使得S[i+1..j+1]均減小1，其中j是使任意i+1<=k<=j0均滿足S[k]（減小前）>M[k]的最大的j0值。
從這個當中可以發現，對于原題的每一個可行方案，必然都是分為若干個階段，其中每一階段是將某個D[i]值減小1（當然，要滿足D[i]在減小前>0），每一階段進行后都會將從S[i+1]開始的連續的一段S值都減小1，恰好可以抽象成一條連續的路徑，又因為當S[i]減小到<=M[i]的時候就必須停止了（準確來說是不能再往后延伸了），所以每個S[i]的能夠繼續延伸的減小的量都是有限的，為初始的S[i]-M[i]（如果這個值<0，則取0），剛好是一個上限。這很明顯是增廣路思想。
所以，經過整理，可以建立一個網絡流模型：
<1>設立兩個源點s和s'（其中s是真正的源點）及匯點t，連邊<s, s'>，容量為K，費用為0，表示最多只能有K個階段；
<2>將每一站i拆成兩個點i'和i''，連邊<i', i''>，容量為max(S[i]-M[i], 0)，費用為0，表示該點最多只能接受max(S[i]-M[i], 0)次加速器作用；
<3>對于所有的i滿足1<=i<N，連邊<(i-1)'', i'>，容量為INF，費用為第i站下車的人數（這是因為即使S[i]<=M[i]，加速器對于本站仍然有效，只是不能繼續延伸，所以表示加速器起的效果的邊應該在本站的限制之前）；
<4>對于所有的i滿足0<=i<N-1，連邊<s', i''>，容量為初始D[i]，費用為0，表示使用加速器的地方，從下一站開始對S[i]起效果；
<5>對于所有的i滿足1<=i<N，連邊<i', t>，容量為INF，費用為0，表示加速器作用的結束。
（其實，0'和(N-1)''這兩個點是木有任何意義的，可以從圖中刪掉）
這樣，每一階段加速器的作用都可以表示為一條從s到t的增廣路，該網絡流模型中的各種限制也反應了題目中的限制。對該網絡求最大費用最大流，得到的總的最大費用從初始的總旅行時間中減去（注意總旅行時間是long long的），即為答案。可以證明，這個模型符合“兩條原則”，所以是正確的。

（2）流量平衡思想：
這個思想的應用非常廣，可以解釋絕大多數網絡流模型。
所謂流量平衡，就是指在一個可行流里，除了源點和匯點外，其余每個點的入邊流量總和都等于出邊流量總和。可以證明，一個流是可行流當且僅當其：（1）每條邊的流量都不超過容量限制；（2）符合流量平衡。
流量平衡思想的主要用處是：可以把圖中的每條邊的流量（當然必須是非負的）都想像為一個變量的值，對于每個點，滿足流量平衡，也就是一些變量的和值滿足某種等量關系，如果這些等量關系剛好能夠反映題目中的所有信息，邊的容量限制也反映題目中的條件，且這個模型符合“兩條原則”，則該模型就是正確的了。在建模的時候，應先單獨考慮各個點，找到它們的所有入邊和出邊代表的變量是什么，然后再將這些邊合并，構成圖。
在用流量平衡建模時有一些技巧：
<1>要注意每條邊都同時作為一個點的出邊和一個點的入邊，因此，每個變量必然同時關聯兩個等量關系，且分別出現在這兩個等量關系的等號的左邊和右邊（或者是以一對相反數形式出現）；
<2>如果題目中給出的變量和值關系不是等量關系，而是不等關系，那么可以將剩余的流量通過從源點或往匯點連邊的辦法，使其平衡。比如，若題目中有y1+y2>=x1+x2>=y1+y2-5這樣的關系，則可以這樣做：設置一個點，將y1、y2代表的邊作為該點的入邊，將x1、x2代表的邊作為該點的出邊，然后從該點往匯點連一條容量為5的邊；
<3>如果點內部有限制（比如某個點自身的權值不能超過X等等），那么該點內部也“暗含”一個變量，此時就需要拆點（不一定拆成兩個點，可能拆成更多的點），然后在拆出的點當中再連邊，附加一些限制，然后再考慮流量平衡；
<4>如果一條邊有上下界，且上下界相等（也就是該邊的流量已經定死了），則可以改裝成費用流，將這條邊的費用設為一個絕對值很大的負數，這樣就肯定能保證該邊滿流了。
例2：餐巾計劃問題（經典問題）
這個的模型用增廣路思想根本就不能解釋。其實，可以用增廣路思想建立一個模型，但是是錯誤的，可以用下面的“兩條原則”檢查出來。
<1>對于每天，要處理的餐巾總數=當天買的餐巾總數+當天洗好的餐巾總數+上一天保留下來的未處理的餐巾總數，這三個當作入邊；
<2>對于每天，要處理的餐巾總數=送快洗部的餐巾總數+送慢洗部的餐巾總數+保存起來留到下一天處理的餐巾總數，這三個都當作出邊；
<3>每天的內部有限制：要用的餐巾總數>=當天的需求量，其實，總可以構造出要用的餐巾總數=當天的需求量的最優方案，所以這些限制其實是上下界相等的。
而<1>和<2>剛好描述了每天這個整體的流量平衡，<3>是一個內部限制，用拆點解決。仔細觀察所有的邊可以發現，“當天洗好的餐巾總數”與“送快洗部的餐巾總數”和“送慢洗部的餐巾總數”可以合并，“上一天保留下來的未處理的餐巾總數”與“保存起來留到下一天處理的餐巾總數”也可以合并。
這樣，可以構造出兩種模型：
1)：第i天拆成兩個點i'和i''，連邊<i', i''>，容量為第i天需求量，費用為0；對于任意0<=i<N-1，連邊<i'', (i+1)''>，容量INF，費用0；對于任意0<=i<N，連邊<S, i'>，容量INF，費用p，連邊<i'', T>，容量INF，費用0；對于任意0<=i<N-m，連邊<i'', (i+m)'>，容量INF，費用f；對于任意0<=i<N-n，連邊<i'', (i+n)'>，容量INF，費用s；求最小費用最大流，最小的總費用就是結果；
2)：第i天拆成兩個點i'和i''，連邊<S, i''>和<i', T>，容量均為第i天需求量，費用均為0；對于任意0<=i<N-1，連邊<i'', (i+1)''>，容量INF，費用0；對于任意0<=i<N，連邊<S, i'>，容量INF，費用p；對于任意0<=i<N-m，連邊<i'', (i+m)'>，容量INF，費用f；對于任意0<=i<N-n，連邊<i'', (i+n)'>，容量INF，費用s；求最小費用最大流，最小的總費用就是結果。
以上兩種模型，看上去都符合題目中的限制，也符合流量平衡，但是，模型1)是錯誤的，模型2)是正確的，這是為什么呢？

（3）判定網絡流模型是否正確的兩個原則：
<1>可行性原則：原題中的每一種可行方案，在建立的網絡流模型中都對應著一個“能求出的”流（一般是滿足一定的條件的流，比如某些邊必須滿流等），注意這里的對應必須是“一一對應”，就是，既不能有可行方案丟失，也不能出現不可行方案；
<2>最優性原則：原題中的最優方案（準確來說是最優方案的結果），在建立的網絡流模型中都對應著一個“能求出的”量（最大流量或者滿足最大流量的前提下的最小費用），也就是，最優結果必須是可以通過這個模型求出的。
一個網絡流模型正確，當且僅當其符合以上兩條原則。
這兩個原則可以檢查所建立的網絡流模型是否正確。比如，對于例2中的兩個模型，模型1)由于最大流對應的是“買的餐巾總數盡可能多”的方案，不是最優方案，因此原題中的最優結果無法求出，顯然不符合最優性原則，因此它是錯誤的。模型2)中，由于可行方案必然能使所有<S, i''>中的邊滿流，且能夠求出，符合可行性原則；最優方案由于<i', T>這條邊的限制，必然是最大流，且是費用最小的最大流，其最小費用為最優結果，符合最優性原則，因此它是正確的。

歷經千辛萬苦總算搞定了COCI 2011 OPEN的所有題……真WS啊囧……
（不過除了sort的滿分算法稍微看了一下題解之外，其它的題目都是自己想出來的……這說明本沙茶想算法的能力并不差……只是所用的時間有點……）

sort：很容易想到該置換的循環分解，然后對每個長度大于1的循環進行一次操作就成了，總操作次數是長度大于1的循環個數。但是，這并不是最優解（在官方數據中，這個算法能過4個點，加上剩下6個點的一半分總共是70分，所以現場結果中多數人都是70分……）。最優解是先通過一次操作把各個長度大于1的循環攪亂，使得整個置換只有一個循環，然后再來一次操作就行了，也就是任何置換都最多只要兩次操作就行……至于攪亂的方法，只要在原來的各個循環（當然是長度大于1的）中各抽出一個元素，再對這些抽出的元素執行一次題目中的操作即可（證明是很容易的）。不過要注意只需0次或1次操作的情況：當原置換長度大于1的循環總數為0或1時；
至于具體的操作構造方法隨便亂搞一下就行了囧……

telka：應該算是最水的一題……樹狀數組的裸模型“改段求段”（具體見這里），唯一值得注意的就是在改段求段模型中的一個注意點：當l=1的時候，不能執行opr(l-1, c)，因為凡是下標遞增的數組都不能以0作為初始下標；

rijeka：這題比較坑人啊囧……如果任意時刻最多只能載一個人，可以把每個人的要求（也就是每條有向線段）都拆成若干個元線段，然后統計正反元線段的個數，亂搞一下就成了……不過這題目里面是可以載任意多的人……那么最優策略是：先把所有反方向線段覆蓋的總區間求出來，比如有4->2、6->3、9->8三條反方向線段，則覆蓋的區間就是[2, 6]和[8, 9]，然后在送人的時候，每送到一個區間的右端就回頭去把這個區間內的要走反方向的人全送到，然后再回頭往正方向開（比如上例中先從0到6，回到2，再從2到9，回到8，再回頭往前一直開到終點），這樣開到終點時，所有的人就都送到了，因此，總時間就是(M+反方向線段覆蓋的總長度)，用線段樹來搞。此外，由于M太大，需要離散化。

后面兩題就是猥瑣題了。

kamion：很明顯是個遞推……但是按照常規方法根本無法劃分狀態。不過，要發現本題和括號序列類的動態規劃神似，因此就可以用括號序列的來搞。關鍵是，對于那些第3種邊（既不含左括號也不含右括號的）比較難搞，另外本題還允許到終點的時候有左括號（就是大寫字母）剩余，這就明顯加大了難度。
狀態設計應是這樣的：F[i][j][k][s0][s1]，表示從i到j走正好k步，且滿足單多段限制（s0）和多余左括號限制（s1）的合法路徑總數，s0、s1為bool，s0表示是單段還是多段的規則括號序列，0：單段，1：單段或多段；s1表示是否可以有多余左括號，0：不能有；1：可以有（當然也可以木有，也就是s0和s1都是0包含在1之中的）。
遞推式：
F[i][j][k][0][0]=ΣF[t1][t2][k-2][1][0]（其中<i, t1>邊有一左括號，<t2, j>邊有一右括號，且兩括號匹配）；
F[i][j][k][1][0]=ΣF[t1][t2][k-2][1][0] + Σ(F[i][t][k'][0][0] * F[t][j][k-k'][0][1]) （注意0<k'<k，其它的類似）；