第七周課程總結

區間DP：盡管很多題目都聽懂了，看著代碼也能理解，但是對于狀態轉移的具體程序事實上大多數只停留在代碼，轉移程序并不清晰，因此要加強狀態轉移的理解，

課上重點例題
題意：一群男生上臺，每人都有一個緊張值，和出場順序k有關（a[i]*(k-1)),有一個小黑屋調整出場順序，相當于堆疊，先進后出，求最小的緊張值的和最小，
題目本身感覺就很難，上課也只是大致聽懂了個思路
識訓：
1.一個問題放在一個大區間內很難想，可以在先在小區間內模擬，本題會出現一個問題，小區間內的模擬會出現一些無效區間---->>>通常將無效區間定為0，而由于本題是求最小值，所以又要求將某些區間設定為無窮大，
到此，對區間的初始化才完成（初始化通常是做dp的第一步，有很多種情況，也是一個難點）
2.狀態轉移方程很難找，很復雜，腦子里想：會想到有很多人需要調換順序的情況，以及調換到哪個位置緊張之最小，都很難處理，
問題解決：
很多人需要調換----->>>首先要明白這是一個大問題，可分解為有很多規模小的子問題（DP特征），也就是先考慮小區間內人員調換最優情況，小規模的人員調動，最后大問題（很多人需要調動的最優）便分解為多個小區間內最優情況的累加，
（不要有畏難情緒，不去深思永遠都是難題，）
一個區間內的人員調換（如下表）
還是有個點還是沒想通，a[i]被放到后面出場，那么dp[i+1,i+k]必然會先出場，那么他們的緊張值為什么沒有因為提前一位出場而變化！??
我最后歸結為，這一部分dp[i+1,i+k]的出場順序不變，因為如果他們提前了一位，那么dp[i+k+1,j]便沒有后移，

A題識訓：
雖然老師給了一套固定模板，我也以為找到狀態方程往里套就行，但實際并非如此，雖然都是一個套路，但也要思考后把模板變化著用，
題意：題目很長，理解還是有點難度，共n場晚會，每場晚會都要穿對應的服飾，可以穿多件衣服，脫下的衣服不能再穿，最少需要多少件衣服，
我的思路：1.直接套用課上固定模板，2.不難發現，就兩種情況，身上有這件衣服，脫下外面衣服來滿足當前晚會；或者就去穿一件新衣服，兩者比較取最小，
區間dp[i][j]的含義不再變化，就是區間兩個端點，相較經典DP少了變化，
問題點：
1.由于每天的晚會順序固定，區間不能跳過天數列舉，模板無法套用，要自己思考如何改，

B題識訓：
1.課上例題，理解起來也不困難，就是不斷列舉區間長度，在去看每個區間的具體情況，但每次看到分隔點k，在區間內起到不斷分隔區間，比較各種情況，都覺得非常巧妙，另外就是對下標臨界點的考慮，
2.由于每個括號不能組成一對，所以初始化為0，這是和A題不同之處，

C題識訓：
我的思路：會發現如果按照題目里的例子思考，會有一個問題：被拿走的牌肯定要刪去，但不知道怎么處理，便轉換思維：保持首尾兩張牌不變，向其中加牌，（模板并不適用）
1.n張牌分解成子區間后，首尾的牌在不斷變化，
2.初始化：當區間長度小于3時，值都為0，

石子合并問題---->>>識訓：
1.當石子都在一條直線上時，正常處理，
注：
若求石子合并最小得分：將dp[i][j]都初始化為無窮大；
若求石子合并的最大得分，將dp[i][j]都初始化為0，
（ dp[i][i]要初始化為0，因為區間是一個點，無法合并）

2.當石子堆陣列成一個圓，收尾相連，處理方式---- >>>由于合并石子的起點無法確定，每堆石子都有可能是起點，所以要將圓轉化為1條直線，使得a[i+n]=a[i],擴大一倍石子堆數，但取的區間長度仍為n，相當于對第一種情況的n次起點不同的合并，
注：
1.長度為n的區間有n個，所以要進行回圈比較來求得最值，不同于一體直線上的dp[1][n],要對dp[i][i+n-1]回圈，
2.相關陣列記得開成2*n，對于分隔區間的那層回圈（第三層），端點要考慮清楚，幾種表示形式都可以，

關于回文字串的區間DP—識訓：
1.將字串改為回文字串，可以洗掉字符或添加字符（代價不同），求出最小代價，
我的思路：挺好想的，如果端點字符相等，則不需要處理；若不相等，比較處理首字符代價和尾字符代價，不相等時轉移方程：

dp[i][j]=min(dp[i+1][j]+cost[s[i]-'a'+1],dp[i][j-1]+cost[s[j]-'a'+1])

注：一點開始沒想通，洗掉字符或添加字符雖然代價不同取最小，但是兩種不同操作會影響后面的狀態---->>>還是沒真正理解DP概念，只要確定子問題的規模和原問題是一樣的，那么只需要關注子問題即可，

2.從一個字串中取任意字符構成回文，最多有多少種取法，
我的思路：先從長度為2的區間進行分析，兩個字符若相等有3種取法；若長度為3，比如形式為“a b a”，取法應該是3+1+1，3個字符單獨構成一個回文，b和兩個a構成一個回文，兩端a單獨構成1個回文，其實到這一步狀態方程也差不多該寫出來了，但還是差一點，忽略了有些回文被重復計數，
容斥定理：簡單來說，就是在兩個區間內可能會取到規模一樣的字串，導致重復計數，統計時先算進來，然后再減掉，

dp[i][j]=dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1]

如果首尾字符相等的話，由三部分組成：
dp[i][j]本身的值+dp[i+1][j-1] (區間內任意一個都可和首尾組成新回文）+1（首尾組成）

3.兩個兔子一個從順時針跳，一個逆時針跳，要求跳的石頭重量相等，且跳過的不能再跳，問最多進行多少回合，
這題沒什么想法，看出好像和回文有關，之后才知道是要找回文非連續序列，而根據回文非連續序列性質，順時針和逆時針走對于一個區間是一樣的，
1.又因為兩個兔子只能碰一次面，也就是最終聚集到同一處，---->>>也就轉化為求一個區間的最長回文非連續序列，
2.由于每個石頭都可能被兔子標記，當作起點，初始化為1，
3.起點不確定，但兩只兔子所走的路程是一樣的（因為要滿足回文），到最后相遇，回合數就等于dp[1][i]+dp[i+1][n]

L題識訓：
對于思路，老師上課講過，幾個注意點
1.定義const int inf為極大值時可用memset(dp,-inf,sizeof(dp));將初始化為負無窮，
2.區間內數全部取得的情況要拿出來和區間dp[i][j]前半區間、后半區間進行比較.
3.一個思維點，根據數學公式2*A-sum的值最大，消元思想，

K題識訓：
我的思路：本題錯誤的將dp[i][j]的含義定為區間的兩個端點，雖然不停變化對m的討論，保證最后一分鐘的疲勞度為0，但沒有辦法控制中間的狀態，始終想不明白，
看完題解，才發現犯了慣性錯誤：雖然大多數題目i，j表示的是一個區間，但本題并不是，方向上就錯了，
1.dp[i][j]表示第i分鐘的j疲勞值（j<=k).
2.兩種狀態，疲勞度為0時，可以選擇在第i分鐘跑步，則累加距離；若選擇休息，則等于上一分鐘的距離，
3.比較疲勞度降到0之前，走的最大距離，感覺這段代碼比較難想，我一直想不到怎么處理，非常巧妙，一個倒推思想，所以放上去，

for(int k=0;i<=m;k++)
{   if(i-k>=0)
    dp[i][0]=max(dp[i][0],dp[i-k][k]
}

博弈補充：
反尼姆博弈：相對于尼姆博弈，最后取得石子的人輸！！
結論：先手必勝的情況，
1.所有堆的石子數都為1，且游戲的SG值為0（也就是偶數），
2.有些堆的石子數大于1且游戲的SG值不為0，（SG的值為所有數的異或結果）

賽后補題
1 Bogosort
將給定陣列逆序排列，元素值大的減去小下標肯定大于元素小的減去大下標，滿足題意，（過）

2. Adding Powers
隊伍當時沒做出來的一題，能理解題意：將0加上k的i次方等于給定的數（i只能用一次），且可以是k的不同i次方相加等于給定的數，
這是之前我們沒涉及的題目，我們的想法只是簡單的列舉，要用到DP記錄，感覺上就行不通，
正解：非常巧妙，將給定的數轉化為k進制，用陣列不斷記錄輸入數對k的取模的值，（進制轉換方式）若用到次數>=2，則輸出“NO”，

3. Digit Game
被一個簡單的思維題卡住了，真的是自己把問題想復雜了，
思路：A對奇數位置上的牌處理，B對偶數位置上的牌進行處理，最后一張牌為奇數，A贏；否則B贏，---->>>我竟然很天真的去統計奇數位置上偶數牌，偶數位置上奇數牌出現次數，傻傻分不清…
實際只需要看奇數位置上是否需要奇數牌，偶數位置上是否出現偶數牌；然后判斷總共牌數即可
注：奇數最后一輪到A，先對A判；偶陣列后一輪到B，先對B判，代碼看似一樣，但含義不一樣，

4.Air Conditioner
很多有價值的想法無法精煉的總結出來，本質就是不斷模擬溫度升降程序：溫度的該變數就是前后兩位客人的差額，如果溫度變化的最大值小于客人最低承受溫度或最小值大于客人最高承受溫度，都無法滿足他，直接輸出no，

5.The Number of Products
本題兩種解法，一種當思維題來做，另一種則是當經典DP來做，算是DP中簡單的那種（類似牛吃藥跳高那題），傾向第二種方法：
1.如果數為正數，那么對于負數的方案數不影響，對于正數的方案數+1（需要一個變數不停地對更新的邊界方案數累加，“1”代表自己本身為正數便可構成一個方案）
2.如果數為負數，那么正數的方案數為上一個邊界負數的方案數（只是起到調整符號的作用），負數的方案數為上一個邊界正數的方案數+1.（本身為負數，所以加1，畫圖！）

----我會不會堅持？我會不會堅持？
----做好自己，送走月亮，