POJ 1226 Substrings

想法：
    先將全部的字串依照length由小到大排序，把最短的那個字串拿來枚舉，由長到短枚舉該字串的所有substring，以sample input第二個case舉例，最短的字串為"rose"，枚舉substring "rose", "ros", "ose", "ro", "os"...。
    每次枚舉到一個substring後，記得還有反轉sub_inverse，把substring和sub_inverse拿來和其他字串(除了最短的字串以外的字串)比較，這邊我是套KMP Algorithm，如果其他字串全部都找的到substring或sub_inverse的話，表示找到答案，輸出該substring的長度。

POJ 3461 Oulipo

題意：
    找出W字串在T字串中出現幾次。例如W="AZA",T="AZAZAZA"，答案為3次。

想法：
    套KMP演算法

UVa 10806 Dijkstra, Dijkstra

題意：
    給你一個無向圖，每條邊有cost，現在問如果不走已經走過的邊，則從S到T，然後再從T到S的最少cost是多少，如果無法達成則輸出"Back to jail"。

想法：
    最小cost最大流，S到T再從T到S，也就是T當作源點，S當作匯點，從T流到S，看是否能流過去2條，如果能則輸出min_cost，否則輸出"Back to jail"。
    因為同一條邊不能重複走，因此可以用一個二維矩陣used[][]，在SPFA找"正向邊"的時候檢查used[i][j]!=true，除了code 82行和96行之外，其他都和MCMF模板一樣。

UVa 10746 Crime Wave - The Sequel

想法：
    銀行編號1~N，警察編號N+1~N+M，源點S=0以及匯點T=N+M+1。一開始先將S連到每間銀行，每個警察連到T，以及每間銀行連到每個警察，以上單向邊容量都為1。
    接下來就是套模板做MCMF，注意輸出的時候因為是double，因為進位問題所以要把答案加上一個極小的數字，例如，如果printf("%.2f", 17.225);，結果是輸出17.22，因此要printf("%.2f", 17.225+0.000000001);才會是正確答案17.23。

UVa 563 Crimewave

想法：
    點與點之間的邊是雙向邊，但是走某一邊後另一邊就不能走了，所以我們把一個點i分成兩個點i和i'，i到i'容量為1，點i建圖的時候：

• cap[i][i']=1
• 假設j在i的上方，cap[i'][j]=1，上下左右依此類推

    然後我們還要有個super source(S)和super sink(T)，把最外面四個邊的點i'連到T，S連到輸入的座標i(也就是銀行的位置)。建完圖後，就是做最大流看結果是否等於銀行的數量即可。

    一開始TLE了，後來用了個vector<int> edge[MAX]來存每個點i能連到哪些點，避免bfs的時候nxt要從0到最後(程式碼81行)，最後時間為1.8s。

UVa 10594 Data Flow

題意：
    給你一個無向圖，兩點之間的邊的容量是K，每條邊有不同的cost，現在有大小為D的資料，要從起點傳到終點，問把全部資料傳過去的最小cost是多少，如果不能全部傳過去則輸出Impossible.

• 第一行輸入N M：總共N個點，編號從1~N，然後底下有M行
• 有M行，每行u v c：表示點u和點v之間的cost為c(雙向圖)
• 最後一行D K：要傳的資料大小為D，每個邊的容量為K

想法：

    最小cost最大流題型(MCMF)，基本上就是建圖，然後套MCMF演算法模板，但提交後發現時間根本是壓秒過@@，花了2.979s(時限3s)，但是這個秒數排名還在前一半以內...。

    不過還是要壓一下秒數，看了同學的code後，發現這題可以最佳化的地方在於"每條邊的容量都是一樣的"，所以你可以把每條邊的容量當成1，然後再乘以K就好了。底下附上兩種code，第一個是差點TLE的模板code，第二個是最佳化的code，兩者的差別只差在MCMF()這個function的寫法。第二個的時間是0.135s， 和原本差了20幾倍。

POJ 2411 Mondriaan's Dream

想法：

狀態壓縮DP，我們定義一列(橫的)一個狀態D：

• 第i位置為1表示這一列位置i和下一列位置i是由直長方形組成(|)
• 第i位置為0表示1以外的情況

注意以上的定義，以這題題目的圖來看，

• 第一列狀態D1=(00100001100)2
• 第二列狀態D2=(11010010000)2
• 第三列狀態D3=(00100001001)2
• 其他列依此類推，最後一列一定全部都是0。

接下來定義dp[i][d] = k，表示第i列在狀態d的情況下有k個方法數。如果能接受的話，那麼根據定義，如果第H列是圖的最後一列，本題答案就是dp[H][0]。

    定義完成後，基本上的做法是從最上面那列開始往下更新，例如第i列狀態a如果能和第i+1列狀態b相鄰(注意任兩個狀態不一定相鄰..)，那麼dp[i+1][b]+=dp[i][a];，就這樣枚舉所有狀態，最後輸出答案dp[H][0]。

    為了簡化code，不用初始化第一列每個狀態方法數是1(因為第一列所有狀態都是可以的)，因此我們直接初始化dp[0][0]=1，令這個假設的第0列狀態0方法數為1。

    另外在做以上的for loop之前，先建個狀態是否可以相鄰的表，令adjacent[i][j] = true表示狀態i在這列而狀態j在下一列是可以相鄰的，如最上面題目example，adjacent[D1][D2]==true，adjacent[D2][D3]==true。

    最後總結一下，為了加速，我們可以總是讓寬比較小高比較大，這樣可以減少每列的狀態數，另外也能用個ans[H][W]來紀錄答案，如果重複的題目就直接輸出即可。

UVa 10364 Square

想法：

    dfs加上各種減支：

1. 如果所有stick的長度和(sum)不能被4整除直接輸出no
2. 如果最長stick的長度已經大於(sum/4)直接輸出no
3. dfs的時候已經排完三個邊直接return true，因為第四個邊一定排得出來
4. 先將stick由大排到小，每次dfs的時候stick不要從第一個開始挑選，而是要從上一層dfs選到的stick的下一個開始選。

基本上第四點是關鍵，有跟沒有就是0.0x秒和TLE的差別。

UVa 11218 KTV

題意：
    總共有9個人(編號1~9)要分成3組唱歌，每組3個人，每個人只能唱一次。第一行N表示底下有N種組合，每種組合a,b,c,s，前三個是人員編號，s是該組合的分數。從N種中任選三種組合使得1~9號都能唱到歌，並且使得分數的和最高，輸出該分數，如果找不到組合滿足大家都能唱到歌則輸出-1。

想法：
    bitmask，(1<<9)-1表示所有人都唱的到歌的狀態，二進位來看就是(111111111)2，dp[i]=j表示在狀態i的情況下最高分數為j，因此dp[(1<<9)-1]就是所有人唱的到歌的最高分數。
    用dfs來枚舉不同組合，當人員沒有重複的時候才能將兩個狀態合併在一起，例如(000000111)2和(000111000)2這兩個狀態可以合併變成(000111111)2，並去更新dp[(000111111)2]的分數，不斷更新所有可能的合併來枚舉所有情況。

UVa 10651 Pebble Solitaire

題意：
    跳棋，例如"oo-"表示第一和第二個位置有棋子，第三個位置是空的，因此第一個位置的棋子可以跳過第二個位置的棋子並取走第二個位置的棋子，變成"--o"。題目給定一個12個位置的棋盤，問經過不斷跳棋後，剩下最少棋子的數量。

想法：
    想到兩種方式：bitmask+bfs或是backtracking，兩種方法其實差不多，都是把所有的情況枚舉，找出最小値。第一種方法為0.009s，第二種為0.012s，時間相差不大，寫backtracking是較簡單的。