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

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

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

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

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

telka：應(yīng)該算是最水的一題……樹狀數(shù)組的裸模型“改段求段”（具體見這里），唯一值得注意的就是在改段求段模型中的一個注意點(diǎn)：當(dāng)l=1的時(shí)候，不能執(zhí)行opr(l-1, c)，因?yàn)榉彩窍聵?biāo)遞增的數(shù)組都不能以0作為初始下標(biāo)；

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

后面兩題就是猥瑣題了。

kamion：很明顯是個遞推……但是按照常規(guī)方法根本無法劃分狀態(tài)。不過，要發(fā)現(xiàn)本題和括號序列類的動態(tài)規(guī)劃神似，因此就可以用括號序列的來搞。關(guān)鍵是，對于那些第3種邊（既不含左括號也不含右括號的）比較難搞，另外本題還允許到終點(diǎn)的時(shí)候有左括號（就是大寫字母）剩余，這就明顯加大了難度。
狀態(tài)設(shè)計(jì)應(yīng)是這樣的：F[i][j][k][s0][s1]，表示從i到j(luò)走正好k步，且滿足單多段限制（s0）和多余左括號限制（s1）的合法路徑總數(shù)，s0、s1為bool，s0表示是單段還是多段的規(guī)則括號序列，0：單段，1：單段或多段；s1表示是否可以有多余左括號，0：不能有；1：可以有（當(dāng)然也可以木有，也就是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，其它的類似）；