取數字游戲 動態規劃
一、高分求動態規劃題目!!!
這是我們計算機系算法設計課的實驗課程，下面是動態規劃內容：
實驗四：動態規劃
實驗目的：理解動態規劃的基本思想，理解動態規劃算法的兩個基本要素最優子結構性質和子問題的重疊性質。熟練掌握典型的動態規劃問題。掌握動態規劃思想分析問題的一般方法，對較簡單的問題能正確分析，設計出動態規劃算法，并能快速編程實現。
實驗內容：編程實現講過的例題：最長公共子序列問題、矩陣連乘問題、凸多邊形最優三角剖分問題、電路布線問題等。本實驗中的問題，設計出算法并編程實現。
習題
1．最長公共子序列
一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列X=
解答如下：
a)最長公共子序列的結構
若用窮舉搜索法，耗時太長，算法需要指數時間。
易證最長公共子序列問題也有最優子結構性質
設序列X=
i.若xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長公共子序列；
ii.若xm≠yn且zk≠xm，則Z是Xm-1和Y的最長公共子序列；
iii.若xm≠yn且zk≠yn，則Z是X和Yn-1的最長公共子序列。
其中Xm-1=
最長公共子序列問題具有最優子結構性質。
b)子問題的遞歸結構
由最長公共子序列問題的最優子結構性質可知，要找出X=
由此遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。例如，在計算X和Y的最長公共子序列時，可能要計算出X和Yn-1及Xm-1和Y的最長公共子序列。而這兩個子問題都包含一個公共子問題，即計算Xm-1和Yn-1的最長公共子序列。
我們來建立子問題的最優值的遞歸關系。用c[i,j]記錄序列Xi和Yj的最長公共子序列的長度。其中Xi=
c)計算最優值
由于在所考慮的子問題空間中，總共只有θ(m*n)個不同的子問題，因此，用動態規劃算法自底向上地計算最優值能提高算法的效率。
計算最長公共子序列長度的動態規劃算法LCS_LENGTH(X,Y)以序列X=
程序如下：
#include
#include
int lcs_length(char x[], char y[]);
int main()
{
char x[100],y[100];
int len;
while(1)
{
scanf("%s%s",x,y);
if(x[0]=='0')//約定第一個字符串以‘0’開始表示結束
break;
len=lcs_length(x,y);
printf("%d\n",len);
}
}
int lcs_length(char x[], char y[])
{
int m,n,i,j,l[100][100];
m=strlen(x);
n=strlen(y);
for(i=0;i l[i][0]=0; for(j=0;j l[0][j]=0; for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(x[i-1]==y[j-1])//i,j從1開始，但字符串是從0開始 l[i][j]=l[i-1][j-1]+1; else if(l[i][j-1]>l[i-1][j]) l[i][j]=l[i][j-1]; else l[i][j]=l[i-1][j]; return l[m][n]; } 由于每個數組單元的計算耗費Ο(1)時間，算法lcs_length耗時Ο(mn)。 思考：空間能節約嗎？ 2．計算矩陣連乘積 在科學計算中經常要計算矩陣的乘積。矩陣A和B可乘的條件是矩陣A的列數等于矩陣B的行數。若A是一個p×q的矩陣，B是一個q×r的矩陣，則其乘積C=AB是一個p×r的矩陣。由該公式知計算C=AB總共需要pqr次的數乘。其標準計算公式為： 現在的問題是，給定n個矩陣{A1,A2,…,An}。其中Ai與Ai+1是可乘的，i=1,2,…,n-1。要求計算出這n個矩陣的連乘積A1A2…An。 遞歸公式： 程序如下： #include int main() { int p[101],i,j,k,r,t,n; int m[101][101];//為了跟講解時保持一致數組從1開始 int s[101][101];//記錄從第i到第j個矩陣連乘的斷開位置 scanf("%d",&n); for(i=0;i<=n;i++) scanf("%d",&p[i]);//讀入p[i]的值(注意：p[0]到p[n]共n+1項) for(i=1;i<=n;i++)//初始化m[i][i]=0 m[i][i]=0; for(r=1;r for(i=1;i { j=i+r;//j為列 m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//給m[i][j]賦初值 s[i][j]=i; for(k=i+1;k { t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; if(t { m[i][j]=t;//m[i][j]取最小值 s[i][j]=k; } } } printf("%d",m[1][n]); } 3．凸多邊形的最優三角剖分 多邊形是平面上一條分段線性的閉曲線。也就是說，多邊形是由一系列首尾相接的直線段組成的。組成多邊形的各直線段稱為該多邊形的邊。多邊形相接兩條邊的連接點稱為多邊形的頂點。若多邊形的邊之間除了連接頂點外沒有別的公共點，則稱該多邊形為簡單多邊形。一個簡單多邊形將平面分為3個部分：被包圍在多邊形內的所有點構成了多邊形的內部；多邊形本身構成多邊形的邊界；而平面上其余的點構成了多邊形的外部。當一個簡單多邊形及其內部構成一個閉凸集時，稱該簡單多邊形為凸多邊形。也就是說凸多邊形邊界上或內部的任意兩點所連成的直線段上所有的點均在該凸多邊形的內部或邊界上。 通常，用多邊形頂點的逆時針序列來表示一個凸多邊形，即P= 若vi與vj是多邊形上不相鄰的兩個頂點，則線段vivj稱為多邊形的一條弦。弦將多邊形分割成凸的兩個子多邊形 凸多邊形最優三角剖分的問題是：給定一個凸多邊形P= 可以定義三角形上各種各樣的權函數W。例如：定義ω(△vivjvk)=|vivj|+|vivk|+|vkvj|，其中，|vivj|是點vi到vj的歐氏距離。相應于此權函數的最優三角剖分即為最小弦長三角剖分。(注意：解決此問題的算法必須適用于任意的權函數) 4．防衛導彈 一種新型的防衛導彈可截擊多個攻擊導彈。它可以向前飛行，也可以用很快的速度向下飛行，可以毫無損傷地截擊進攻導彈，但不可以向后或向上飛行。但有一個缺點，盡管它發射時可以達到任意高度，但它只能截擊比它上次截擊導彈時所處高度低或者高度相同的導彈。現對這種新型防衛導彈進行測試，在每一次測試中，發射一系列的測試導彈（這些導彈發射的間隔時間固定，飛行速度相同），該防衛導彈所能獲得的信息包括各進攻導彈的高度，以及它們發射次序。現要求編一程序，求在每次測試中，該防衛導彈最多能截擊的進攻導彈數量，一個導彈能被截擊應滿足下列兩個條件之一： a)它是該次測試中第一個被防衛導彈截擊的導彈； b)它是在上一次被截擊導彈的發射后發射，且高度不大于上一次被截擊導彈的高度的導彈。 輸入數據：第一行是一個整數n，以后的n各有一個整數表示導彈的高度。 輸出數據：截擊導彈的最大數目。 分析：定義l[i]為選擇截擊第i個導彈，從這個導彈開始最多能截擊的導彈數目。 由于選擇了第i枚導彈，所以下一個要截擊的導彈j的高度要小于等于它的高度，所以l[i]應該等于從i＋1到n的每一個j，滿足h[j]<=h[i]的j中l[j]的最大值。 程序如下： #include int main() { int i,j,n,max,h[100],l[100]; scanf("%d",&n); for(i=0;i scanf("%d",&h[i]); l[n-1]=1; for(i=n-2;i>=0;i--) { max=0; for(j=i+1;j if(h[i]>h[j]&&max max=l[j]; l[i]=max+1; } printf("%d",l[0]); } 5．石子合并 在一個圓形操場的四周擺放著n堆石子(n<= 100)，現要將石子有次序地合并成一堆。規定每次只能選取相鄰的兩堆合并成新的一堆,并將新的一堆的石子數,記為該次合并的得分。編一程序，由文件讀入堆棧數n及每堆棧的石子數(<=20)。 選擇一種合并石子的方案,使得做n－1次合并,得分的總和最小； 輸入數據： 第一行為石子堆數n； 第二行為每堆的石子數,每兩個數之間用一個空格分隔。 輸出數據： 從第一至第n行為得分最小的合并方案。第n+1行是空行.從第n+2行到第2n+1行是得分最大合并方案。每種合并方案用n行表示，其中第i行(1<=i<=n)表示第i次合并前各堆的石子數(依順時針次序輸出，哪一堆先輸出均可)。要求將待合并的兩堆石子數以相應的負數表示。 Sample Input 4 4 5 9 4 Sample Output －4 5 9－4 －8－5 9 －13－9 22 4－5－9 4 4－14－4 －4－18 22 6．最小代價子母樹 設有一排數，共n個，例如：22 14 7 13 26 15 11。任意2個相鄰的數可以進行歸并，歸并的代價為該兩個數的和,經過不斷的歸并，最后歸為一堆，而全部歸并代價的和稱為總代價，給出一種歸并算法，使總代價為最小。 輸入、輸出數據格式與“石子合并”相同。 Sample Input 4 12 5 16 4 Sample Output －12－5 16 4 17－16－4 －17－20 37 7．商店購物 某商店中每種商品都有一個價格。例如，一朵花的價格是2 ICU(ICU是信息學競賽的貨幣的單位）；一個花瓶的價格是5 ICU。為了吸引更多的顧客，商店提供了特殊優惠價。特殊優惠商品是把一種或幾種商品分成一組。并降價銷售。例如：3朵花的價格不是6而是5 ICU；2個花瓶加1朵花是10 ICU不是12 ICU。 編一個程序，計算某個顧客所購商品應付的費用。要充分利用優惠價以使顧客付款最小。請注意，你不能變更顧客所購商品的種類及數量，即使增加某些商品會使付款總數減小也不允許你作出任何變更。假定各種商品價格用優惠價如上所述，并且某顧客購買物品為：3朵花和2個花瓶。那么顧客應付款為14 ICU因為： 1朵花加2個花瓶優惠價：10 ICU 2朵花正常價：4 ICU 輸入數據：第一個文件INPUT．TXT描述顧客所購物品（放在購物筐中）;第二個文件描述商店提供的優惠商品及價格（文件名為OFF ER．TXT）。兩個文件中都只用整數。 第一個文件INPUT．TXT的格式為:第一行是一個數字B（0≤B≤5），表示所購商品種類數。下面共B行，每行中含3個數C，K，P。 C代表商品的編碼（每種商品有一個唯一的編碼），1≤C≤999。K代表該種商品購買總數，1≤K≤5。P是該種商品的正常單價（每件商品的價格），1≤P≤999。請注意，購物筐中最多可放5*5＝25件商品。 第二個文件OFFER．TXT的格式為:第一行是一個數字S（0≤S≤9 9），表示共有S種優惠。下面共S行，每一行描述一種優惠商品的組合中商品的種類。下面接著是幾個數字對（C，K），其中C代表商品編碼，1≤C≤9 99。K代表該種商品在此組合中的數量，1≤K≤5。本行最后一個數字P（1≤ P≤9999）代表此商品組合的優惠價。當然，優惠價要低于該組合中商品正常價之總和。 輸出數據：在輸出文件OUTPUT．TXT中寫一個數字（占一行），該數字表示顧客所購商品（輸入文件指明所購商品）應付的最低貨款。 8．旅游預算 一個旅行社需要估算乘汽車從某城市到另一城市的最小費用，沿路有若干加油站，每個加油站收費不一定相同。旅游預算有如下規則： 若油箱的油過半，不停車加油，除非油箱中的油不可支持到下一站；每次加油時都加滿；在一個加油站加油時，司機要花費2元買東西吃；司機不必為其他意外情況而準備額外的油；汽車開出時在起點加滿油箱；計算精確到分（1元=100分）。編寫程序估計實際行駛在某路線所需的最小費用。 輸入數據：從當前目錄下的文本文件“route.dat”讀入數據。按以下格式輸入若干旅行路線的情況： 第一行為起點到終點的距離（實數） 第二行為三個實數，后跟一個整數，每兩個數據間用一個空格隔開。其中第一個數為汽車油箱的容量（升），第二個數是每升汽油行駛的公里數，第三個數是在起點加滿油箱的費用，第四個數是加油站的數量。（〈=50）。接下去的每行包括兩個實數，每個數據之間用一個空格分隔，其中第一個數是該加油站離起點的距離，第二個數是該加油站每升汽油的價格（元/升）。加油站按它們與起點的距離升序排列。所有的輸入都有一定有解。 輸出數據：答案輸出到當前目錄下的文本文件“route.out”中。該文件包括兩行。第一行為一個實數和一個整數，實數為旅行的最小費用，以元為單位，精確到分，整數表示途中加油的站的N。第二行是N個整數，表示N個加油的站的編號，按升序排列。數據間用一個空格分隔，此外沒有多余的空格。 Sample Input 516.3 38.09 1 15.7 22.1 20.87 3 2 125.4 1.259 297.9 1.129 345.2 0.999 Sample Output 38.09 1 2 9．皇宮看守 太平王世子事件后，陸小鳳成了皇上特聘的御前一品侍衛。皇宮以午門為起點，直到后宮嬪妃們的寢宮，呈一棵樹的形狀；某些宮殿間可以互相望見。大內保衛森嚴，三步一崗，五步一哨，每個宮殿都要有人全天候看守，在不同的宮殿安排看守所需的費用不同。可是陸小鳳手上的經費不足，無論如何也沒法在每個宮殿都安置留守侍衛。 請你編程計算幫助陸小鳳布置侍衛，在看守全部宮殿的前提下，使得花費的經費最少。 輸入數據：輸入數據由文件名為intput.txt的文本文件提供。輸入文件中數據表示一棵樹，描述如下： 第1行 n，表示樹中結點的數目。 第2行至第n+1行，每行描述每個宮殿結點信息，依次為：該宮殿結點標號i（0 對于一個n（0< n<= 1500）個結點的樹，結點標號在1到n之間，且標號不重復。 輸出數據：輸出到output.txt文件中。輸出文件僅包含一個數，為所求的最少的經費。 如右圖的輸入數據示例： Sample Input 6 1 30 3 2 3 4 2 16 2 5 6 3 5 0 4 4 0 5 11 0 6 5 0 Sample Output 25 10．游戲室問題 有一個游戲室里有多個游戲室，并且這每個游戲室里還有多個游戲室，每個游戲室里面還有游戲室，依此類推。進入每個游戲室都可得到一定的快樂，每個游戲室的門票價格都大于等于0，都有一個快樂值，并且只有進入了一個游戲室，才可以進入它內部的游戲室，小明現在有n元錢，問最大能得到多少的快樂。 11．*基因問題 已知兩個基因序列如s：AGTAGT；t：ATTAG。現要你給序列中增加一些空格后，首先使得兩個序列的長度相等，其次兩個串對應符號匹配得到的值最大。基因只有四種分別用A、G、C、T表示，匹配中不允許兩個空格相對應，任意兩符號的匹配值由下表給出： A G C T〕 A 5-2-1-2-4 G-2 5-4-3-2 C-1-4 5-5-1 T-2-3-5 5-2 〕-4-2-1-2 提示：定義問題l[i][j]為取第一個序列的前i項，和第二個序列的前j項，這兩個序列加空格匹配的最大值。它的最優值與三個子問題有關，l[i-1][j-1]、l[i][j-1]、l[i-1][j]。 建立遞歸公式如下： 其中m[0][t[j]表示表中空格和t[j]匹配的對應值。 思考：本問題的初始化。 12．*田忌賽馬 田忌與齊王賽馬，雙方各有n匹馬參賽（n<=100），每場比賽賭注為1兩黃金，現已知齊王與田忌的每匹馬的速度，并且齊王肯定是按馬的速度從快到慢出場，現要你寫一個程序幫助田忌計算他最好的結果是贏多少兩黃金（輸用負數表示）。 分析：先排序，齊王的馬的速度放在數組a中，田忌的馬的速度放在數組b中。本問題應用的算法是動態規劃和貪心算法相結合解決的。從兩人的最弱的馬入手： 若田忌的馬快，就讓這兩匹馬比賽； 若田忌的馬慢，干脆就讓他對付齊王最快的馬； 若兩匹馬的速度相等，這時有兩種選擇方案，或者它倆比賽，或者對付齊王最快的馬。 定義子問題：l(i，j)為齊王的從第i匹馬開始的j匹馬與田忌的最快的j匹馬比賽，田忌所獲得的最大收益。 則： 程序具體實現時，為了適合c數據從0開始，稍加變動，定義子問題：l(i，j)為齊王的從第i匹馬開始到第i＋j匹馬共j+1匹馬與田忌的最快的j+1匹馬比賽，田忌所獲得的最大收益。初始化時：l[i][0]表示齊王的第i匹馬與田忌最快的馬比賽的結果。 程序如下： #include void readdata(); void init(); int n,a[100],b[100],l[100][100]; int main() { int i,j; readdata(); init(); for(i=n-2;i>=0;i--) for(j=1;j if(a[i+j] l[i][j]=l[i][j-1]+1; else if(a[i+j]>b[j]) l[i][j]=l[i+1][j-1]-1; else if(l[i+1][j-1]-1>l[i][j-1]) l[i][j]=l[i+1][j-1]-1; else l[i][j]=l[i][j-1]; printf("%d",l[0][n-1]); } void readdata() { int i; scanf("%d",&n); for(i=0;i scanf("%d",&a[i]); for(i=0;i scanf("%d",&b[i]); } void init() { int i; // qsort(a,n);//略 for(i=0;i { if(a[i] l[i][0]=1; else if(a[i]==b[0]) l[i][0]=0; else l[i][0]=-1; } } 按照優先順序選擇對應的模塊 /* A若j的右邊有連續3列與它高度相同，選擇方塊（0），從j降落。 B若j==0，且其右邊比他“低”3格；或j==8，且其左邊比他“低”3格；（或更多） 或j在中間，且其左右兩邊都比他“低”3格。則選擇方塊（1），從j降落。 C若j的右邊有連續2列與它高度相同， 若j==0，選擇方塊（18），從j降落； 若j==6，選擇方塊（12），從j降落； 否則，選擇方塊（2），從j降落。 D若j的右邊第1列與他高度相同， 若比左邊的高2，比右邊第2列高1，選擇方塊（6），從j降落； 若比左邊的高1，比右邊第2列高2，選擇方塊（8），從j降落； 否則，選擇方塊（10），從j降落。 E若j>0，且其左邊比他“低”2格，選擇方塊（13），從j降落。 F若j<8，且其右邊比他“低”2格，選擇方塊（17），從j降落。 G若j的左邊有連續2列都比它“低”1格，選擇方塊（16），從j降落； H若j的右邊有連續2列都比它“低”1格，選擇方塊（14），從j降落； I若j的左右兩邊都比它“低”1格，選擇方塊（4），從j降落； 若j的右邊比它“低”1格，選擇方塊（5），從j降落； 若j的左邊比它“低”1格，選擇方塊（3），從j降落。 */ if(hCol< 6&& h== hright1&& h== hright2&& h== hright3) return 0; else if((hCol== 0&& h-hright1>=3) ||(hCol== 8&& h-hleft1>=3) ||(hCol> 0&& hCol< 8&& h-hright1>=3&& h-hleft1>=3)) return 1; else if(hCol== 0&& h== hright1&& h== hright2) return 18; else if(hCol== 6&& h== hright1&& h== hright2) return 12; else if(hCol< 6&& h== hright1&& h== hright2) return 2; else if(h== hright1) { if((h-hright2==1)&&((hCol< 7&& h-hleft1>= 2)|| hCol==7)) return 6; else if((h-hleft1== 1)&&((hCol> 1&& h-hright2>= 2)|| hCol==1)) return 8; else return 10; } else if(hCol> 0&& h-hleft1==2) return 13; else if(hCol< 8&& h-hright1==2) return 17; else if(hCol> 1&& h-hleft1==1&& h-hleft2==1) return 16; else if(hCol< 7&& h-hright1==1&& h-hright2==1) return 14; else if(hCol> 0&& hCol< 8&& h-hright1==1&& h-hleft1==1) return 4; else if(hCol> 0&& h-hleft1==1) return 3; else if(hCol< 8&& h-hright1==1) return 5; } int Diamond::Choose2(int hCol)//按照優先順序選擇對應的模塊 { int h= GetHeight(MaxRow-1, hCol);//讀取hCol列的高度 int hleft1= MaxRow;//位于hCol列左邊第1列的高度 int hleft2= MaxRow;//位于hCol列左邊第2列的高度 int hright1= MaxRow;//位于hCol列右邊第1列的高度 int hright2= MaxRow;//位于hCol列右邊第2列的高度 int hright3= MaxRow;//位于hCol列右邊第3列的高度 if(hCol> 0)//讀取hCol列左邊第1列的高度 hleft1= GetHeight(MaxRow-1, hCol-1); if(hCol> 1)//讀取hCol列左邊第2列的高度 hleft2= GetHeight(MaxRow-1, hCol-2); if(hCol< 6)//讀取hCol列右邊第3列的高度 hright3= GetHeight(MaxRow-1, hCol+3); if(hCol< 7)//讀取hCol列右邊第2列的高度 hright2= GetHeight(MaxRow-1, hCol+2); if(hCol< 8)//讀取hCol列右邊第1列的高度 hright1= GetHeight(MaxRow-1, hCol+1); /////////////按照優先順序選擇對應的模塊////////////////////////////////// /* A若j的右邊有連續3列與它高度相同，選擇方塊（0），從j降落。 B若j==0，且其右邊比他“低”3格；或j==8，且其左邊比他“低”3格；（或更多） 或j在中間，且其左右兩邊都比他“低”3格。則選擇方塊（1），從j降落。 C若j的右邊有連續2列與它高度相同， 若j==0，選擇方塊（18），從j降落； 若j==6，選擇方塊（12），從j降落； 否則，選擇方塊（2），從j降落。 D若j的右邊第1列與他高度相同， 若比左邊的高2，比右邊第2列高1，選擇方塊（6），從j降落； 若比左邊的高1，比右邊第2列高2，選擇方塊（8），從j降落； 否則，選擇方塊（10），從j降落。 E若j的左邊有連續2列都比它“低”1格，選擇方塊（16），從j降落； F若j的右邊有連續2列都比它“低”1格，選擇方塊（14），從j降落； G若j>0，且其左邊比他“低”2格，選擇方塊（13），從j降落。 H若j<8，且其右邊比他“低”2格，選擇方塊（17），從j降落。 I若j的左右兩邊都比它“低”1格，選擇方塊（4），從j降落； 若j的右邊比它“低”1格，選擇方塊（5），從j降落； 若j的左邊比它“低”1格，選擇方塊（3），從j降落。 */ if(hCol< 6&& h== hright1&& h== hright2&& h== hright3) return 0; else if((hCol== 0&& h-hright1>=3) ||(hCol== 8&& h-hleft1>=3) ||(hCol> 0&& hCol< 8&& h-hright1>=3&& h-hleft1>=3)) return 1; else if(hCol== 0&& h== hright1&& h== hright2) return 18; else if(hCol== 6&& h== hright1&& h== hright2) return 12; else if(hCol< 6&& h== hright1&& h== hright2) return 2; else if(h== hright1) { if((h-hright2==1)&&((hCol< 7&& h-hleft1>= 2)|| hCol==7)) return 6; else if((h-hleft1== 1)&&((hCol> 1&& h-hright2>= 2)|| hCol==1)) return 8; else return 10; } else if(hCol> 1&& h-hleft1==1&& h-hleft2==1) return 16; else if(hCol< 7&& h-hright1==1&& h-hright2==1) return 14; else if(hCol> 0&& h-hleft1==2) return 13; else if(hCol< 8&& h-hright1==2) return 17; else if(hCol> 0&& hCol< 8&& h-hright1==1&& h-hleft1==1) return 4; else if(hCol> 0&& h-hleft1==1) return 3; else if(hCol< 8&& h-hright1==1) return 5; } int Diamond::Choose3(int hCol)//按照優先順序選擇對應的模塊 { int h= GetHeight(MaxRow-1, hCol);//讀取hCol列的高度 int hleft1= MaxRow;//位于hCol列左邊第1列的高度 int hleft2= MaxRow;//位于hCol列左邊第2列的高度 int hright1= MaxRow;//位于hCol列右邊第1列的高度 int hright2= MaxRow;//位于hCol列右邊第2列的高度 int hright3= MaxRow;//位于hCol列右邊第3列的高度 if(hCol> 0)//讀取hCol列左邊第1列的高度 hleft1= GetHeight(MaxRow-1, hCol-1); if(hCol> 1)//讀取hCol列左邊第2列的高度 hleft2= GetHeight(MaxRow-1, hCol-2); if(hCol< 6)//讀取hCol列右邊第3列的高度 hright3= GetHeight(MaxRow-1, hCol+3); if(hCol< 7)//讀取hCol列右邊第2列的高度 hright2= GetHeight(MaxRow-1, hCol+2); if(hCol< 8)//讀取hCol列右邊第1列的高度 hright1= GetHeight(MaxRow-1, hCol+1); /////////////按照優先順序選擇對應的模塊////////////////////////////////// /* A若j的右邊有連續3列與它高度相同，選擇方塊（0），從j降落。 B若j==0，且其右邊比他“低”3格；或j==8，且其左邊比他“低”3格；（或更多） 或j在中間，且其左右兩邊都比他“低”3格。則選擇方塊（1），從j降落。 C若j的右邊有連續2列與它高度相同， 若j==0，選擇方塊（18），從j降落； 若j==6，選擇方塊（12），從j降落； 否則，選擇方塊（2），從j降落。 D若j的右邊第1列與他高度相同， 若比左邊的高2，比右邊第2列高1，選擇方塊（6），從j降落； 若比左邊的高1，比右邊第2列高2，選擇方塊（8），從j降落； 否則，選擇方塊（10），從j降落。 E若j==1，且其左邊的列比它“低”1格，或者j>1，且其左邊的第1列比它“低”1格， 左邊的第2列比它“低”2格，選擇方塊（7），從j降落； F若j==7，且其右邊的列比它“低”1格，或者j<7，且其右左邊的第1列比它“低”1格， 右邊的第2列比它“低”2格，選擇方塊（9），從j降落； G若j>0，且其左邊比他“低”2格，選擇方塊（13），從j降落。 H若j<8，且其右邊比他“低”2格，選擇方塊（17），從j降落。 I若j的左邊有連續2列都比它“低”1格，選擇方塊（16），從j降落； G若j的右邊有連續2列都比它“低”1格，選擇方塊（14），從j降落； K若j的左右兩邊都比它“低”1格，選擇方塊（4），從j降落； 若j的右邊比它“低”1格，選擇方塊（5），從j降落； 若j的左邊比它“低”1格，選擇方塊（3），從j降落。 */ if(hCol< 6&& h== hright1&& h== hright2&& h== hright3) return 0; else if((hCol== 0&& h-hright1>=3) ||(hCol== 8&& h-hleft1>=3) ||(hCol> 0&& hCol< 8&& h-hright1>=3&& h-hleft1>=3)) return 1; else if(hCol== 0&& h== hright1&& h== hright2) return 18; else if(hCol== 6&& h== hright1&& h== hright2) return 12; else if(hCol< 6&& h== hright1&& h== hright2) return 2; else if(h== hright1) { if((h-hright2==1)&&((hCol< 7&& h-hleft1>= 2)|| hCol==7)) return 6; else if((h-hleft1== 1)&&((hCol> 1&& h-hright2>= 2)|| hCol==1)) return 8; else return 10; } else if((hCol== 1&& h-hleft1==1)||(hCol> 1&& h-hleft1==1&& h-hleft2==2)) return 7; else if((hCol== 7&& h-hright1==1)||(hCol< 7&& h-hright1==1&& h-hright2==2)) return 9; else if(hCol> 0&& h-hleft1==2) return 13; else if(hCol< 8&& h-hright1==2) return 17; else if(hCol> 1&& h-hleft1==1&& h-hleft2==1) return 16; else if(hCol< 7&& h-hright1==1&& h-hright2==1) return 14; else if(hCol> 0&& hCol< 8&& h-hright1==1&& h-hleft1==1) return 4; else if(hCol> 0&& h-hleft1==1) return 3; else if(hCol< 8&& h-hright1==1) return 5; } int Diamond::Choose4(int hCol)//按照優先順序選擇對應的模塊 { int h= GetHeight(MaxRow-1, hCol);//讀取hCol列的高度 int hleft1= MaxRow;//位于hCol列左邊第1列的高度 int hleft2= MaxRow;//位于hCol列左邊第2列的高度 int hright1= MaxRow;//位于hCol列右邊第1列的高度 int hright2= MaxRow;//位于hCol列右邊第2列的高度 int hright3= MaxRow;//位于hCol列右邊第3列的高度 if(hCol> 0)//讀取hCol列左邊第1列的高度 hleft1= GetHeight(MaxRow-1, hCol-1); if(hCol> 1)//讀取hCol列左邊第2列的高度 hleft2= GetHeight(MaxRow-1, hCol-2); if(hCol< 6)//讀取hCol列右邊第3列的高度 hright3= GetHeight(MaxRow-1, hCol+3); if(hCol< 7)//讀取hCol列右邊第2列的高度 hright2= GetHeight(MaxRow-1, hCol+2); if(hCol< 8)//讀取hCol列右邊第1列的高度 hright1= GetHeight(MaxRow-1, hCol+1); /////////////按照優先順序選擇對應的模塊////////////////////////////////// /* A若j的右邊有連續3列與它高度相同，選擇方塊（0），從j降落。 B若j==0，且其右邊比他“低”3格；或j==8，且其左邊比他“低”3格；（或更多） 或j在中間，且其左右兩邊都比他“低”3格。則選擇方塊（1），從j降落。 C若j的右邊有連續2列與它高度相同， 若j==0，選擇方塊（18），從j降落； 若j==6，選擇方塊（12），從j降落； 否則，選擇方塊（2），從j降落。 D若j的右邊第1列與他高度相同， 若比左邊的高2，比右邊第2列高1，選擇方塊（6），從j降落； 若比左邊的高1，比右邊第2列高2，選擇方塊（8），從j降落； 否則，選擇方塊（10），從j降落。 E若j==1，且其左邊的列比它“低”1格，或者j>1，且其左邊的第1列比它“低”1格， 左邊的第2列比它“低”2格，選擇方塊（7），從j降落； F若j==7，且其右邊的列比它“低”1格，或者j<7，且其右左邊的第1列比它“低”1格， 右邊的第2列比它“低”2格，選擇方塊（9），從j降落； G若j的左邊有連續2列都比它“低”1格，選擇方塊（16），從j降落； H若j的右邊有連續2列都比它“低”1格，選擇方塊（14），從j降落； I若j>0，且其左邊比他“低”2格，選擇方塊（13），從j降落。 J若j<8，且其右邊比他“低”2格，選擇方塊（17），從j降落。 K若j的左右兩邊都比它“低”1格，選擇方塊（4），從j降落； 若j的右邊比它“低”1格，選擇方塊（5），從j降落； 若j的左邊比它“低”1格，選擇方塊（3），從j降落。 */ if(hCol< 6&& h== hright1&& h== hright2&& h== hright3) return 0; else if((hCol== 0&& h-hright1>=3) ||(hCol== 8&& h-hleft1>=3) ||(hCol> 0&& hCol< 8&& h-hright1>=3&& h-hleft1>=3)) return 1; else if(hCol== 0&& h== hright1&& h== hright2) return 18; else if(hCol== 6&& h== hright1&& h== hright2) return 12; else if(hCol< 6&& h== hright1&& h== hright2) return 2; else if(h== hright1) { if((h-hright2==1)&&((hCol< 7&& h-hleft1>= 2)|| hCol==7)) return 6; else if((h-hleft1== 1)&&((hCol> 1&& h-hright2>= 2)|| hCol==1)) return 8; else return 10; } else if((hCol== 1&& h-hleft1==1)||(hCol> 1&& h-hleft1==1&& h-hleft2==2)) return 7; else if((hCol== 7&& h-hright1==1)||(hCol< 7&& h-hright1==1&& h-hright2==2)) return 9; else if(hCol> 1&& h-hleft1==1&& h-hleft2==1) return 16; else if(hCol< 7&& h-hright1==1&& h-hright2==1) return 14; else if(hCol> 0&& h-hleft1==2) return 13; else if(hCol< 8&& h-hright1==2) return 17; else if(hCol> 0&& hCol< 8&& h-hright1==1&& h-hleft1==1) return 4; else if(hCol> 0&& h-hleft1==1) return 3; else if(hCol< 8&& h-hright1==1) return 5; } void Diamond::GetShape(int choice, int hCol) { switch(choice) { case 0: Shape0(hCol); break; case 1: Shape1(hCol); break; case 2: Shape2(hCol); break; case 3: Shape3(hCol); break; case 4: Shape4(hCol); break; case 5: Shape5(hCol); break; case 6: Shape6(hCol); break; case 7: Shape7(hCol); break; case 8: Shape8(hCol); break; case 9: Shape9(hCol); break; case 10: Shape10(hCol); break; case 12: Shape12(hCol); break; case 13: Shape13(hCol); break; case 14: Shape14(hCol); break; case 16: Shape16(hCol); break; case 17: Shape17(hCol); break; case 18: Shape18(hCol); break; default: break; } } void Diamond::Shape0(int hCol) { //**** // 0000 // 0000 map[MaxRow-1][hCol]='*'; map[MaxRow-1][hCol+1]='*'; map[MaxRow-1][hCol+2]='*'; map[MaxRow-1][hCol+3]='*';// PrintMap(); getchar(); int h= GetHeight(MaxRow-2, hCol); for(int i=0; i<4; i++) MovePart(MaxRow-2, hCol+i, h); } void Diamond::Shape1(int hCol) { //*000 //*000 //*000 //*000 map[MaxRow-1][hCol]='*'; map[MaxRow-2][hCol]='*'; map[MaxRow-3][hCol]='*'; map[MaxRow-4][hCol]='*'; int h= GetHeight(MaxRow-5, hCol);// cout<< h< MovePart(MaxRow-5, hCol, h); } void Diamond::Shape2(int hCol) { // 0*00 //***0 // 0000 map[MaxRow-1][hCol+1]='*'; map[MaxRow-2][hCol]='*'; map[MaxRow-2][hCol+1]='*'; map[MaxRow-2][hCol+2]='*'; int h= GetHeight(MaxRow-3, hCol);//cout<< h< for(int i=0; i<3; i++) MovePart(MaxRow-3, hCol+i, h); } void Diamond::Shape3(int hCol) { // 0*00 //**00 // 0*00 map[MaxRow-1][hCol]='*'; map[MaxRow-2][hCol-1]='*'; map[MaxRow-2][hCol]='*'; map[MaxRow-3][hCol]='*'; int h= GetHeight(MaxRow-4, hCol);// cout<< h< MovePart(MaxRow-3, hCol-1, h); MovePart(MaxRow-4, hCol, h); } void Diamond::Shape4(int hCol) { //***0 // 0*00 // 0000 map[MaxRow-1][hCol-1]='*'; map[MaxRow-1][hCol]='*'; map[MaxRow-1][hCol+1]='*'; map[MaxRow-2][hCol]='*'; int h= GetHeight(MaxRow-3, hCol);// cout<< h< MovePart(MaxRow-2, hCol-1, h); MovePart(MaxRow-3, hCol, h); MovePart(MaxRow-2, hCol+1, h); } void Diamond::Shape5(int hCol) { //*000 //**00 //*000 map[MaxRow-1][hCol]='*'; map[MaxRow-2][hCol]='*'; map[MaxRow-2][hCol+1]='*'; map[MaxRow-3][hCol]='*'; int h= GetHeight(MaxRow-4, hCol);// cout<< h< MovePart(MaxRow-4, hCol, h); MovePart(MaxRow-3, hCol+1, h); } void Diamond::Shape6(int hCol) { // 0**0 //**00 // 0000 map[MaxRow-1][hCol+1]='*'; map[MaxRow-1][hCol+2]='*'; map[MaxRow-2][hCol]='*'; map[MaxRow-2][hCol+1]='*'; int h= GetHeight(MaxRow-3, hCol);// cout<< h< MovePart(MaxRow-3, hCol, h); MovePart(MaxRow-3, hCol+1, h); MovePart(MaxRow-2, hCol+2, h); } void Diamond::Shape7(int hCol) { //*000 //**00 // 0*00 map[MaxRow-1][hCol-1]='*'; map[MaxRow-2][hCol-1]='*'; map[MaxRow-2][hCol]='*'; map[MaxRow-3][hCol]='*'; int h= GetHeight(MaxRow-4, hCol);// cout<< h< MovePart(MaxRow-3, hCol-1, h); MovePart(MaxRow-4, hCol, h); } void Diamond::Shape8(int hCol) { //**00 // 0**0 // 0000 map[MaxRow-1][hCol-1]='*'; map[MaxRow-1][hCol]='*'; map[MaxRow-2][hCol]='*'; map[MaxRow-2][hCol+1]='*'; int h= GetHeight(MaxRow-3, hCol);// cout<< h< MovePart(MaxRow-2, hCol-1, h); MovePart(MaxRow-3, hCol, h); MovePart(MaxRow-3, hCol+1, h); } void Diamond::Shape9(int hCol) { // 0*00 //**00 //*000 map[MaxRow-1][hCol+1]='*'; map[MaxRow-2][hCol]='*'; map[MaxRow-2][hCol+1]='*'; map[MaxRow-3][hCol]='*'; int h= GetHeight(MaxRow-4, hCol);// cout<< h< MovePart(MaxRow-4, hCol, h); MovePart(MaxRow-3, hCol+1, h); } void Diamond::Shape10(int hCol) { //**00 //**00 // 0000 map[MaxRow-1][hCol]='*'; map[MaxRow-1][hCol+1]='*'; map[MaxRow-2][hCol]='*'; map[MaxRow-2][hCol+1]='*'; int h= GetHeight(MaxRow-3, hCol);// cout<< h< MovePart(MaxRow-3, hCol, h); MovePart(MaxRow-3, hCol+1, h); } void Diamond::Shape12(int hCol) { // 00*0 //***0 // 0000 map[MaxRow-1][hCol+2]='*'; map[MaxRow-2][hCol]='*'; map[MaxRow-2][hCol+1]='*'; map[MaxRow-2][hCol+2]='*'; int h= GetHeight(MaxRow-3, hCol);// cout<< h< for(int i=0; i<3; i++) MovePart(MaxRow-3, hCol+i, h); } void Diamond::Shape13(int hCol) { //**00 // 0*00 // 0*00 map[MaxRow-1][hCol-1]='*'; map[MaxRow-1][hCol]='*'; map[MaxRow-2][hCol]='*'; map[MaxRow-3][hCol]='*'; int h= GetHeight(MaxRow-4, hCol);// cout<< h< MovePart(MaxRow-2, hCol-1, h); MovePart(MaxRow-4, hCol, h); } void Diamond::Shape14(int hCol) { //***0 //*000 // 0000 map[MaxRow-1][hCol]='*'; map[MaxRow-2][hCol]='*'; map[MaxRow-1][hCol+1]='*'; map[MaxRow-1][hCol+2]='*'; int h= GetHeight(MaxRow-3, hCol);// cout<< h< MovePart(MaxRow-3, hCol, h); MovePart(MaxRow-2, hCol+1, h); MovePart(MaxRow-2, hCol+2, h); } void Diamond::Shape16(int hCol) { //***0 // 00*0 // 0000 map[MaxRow-1][hCol-2]='*'; map[MaxRow-1][hCol-1]='*'; map[MaxRow-1][hCol]='*'; map[MaxRow-2][hCol]='*'; int h= GetHeight(MaxRow-3, hCol);// cout<< h< MovePart(MaxRow-2, hCol-2, h); MovePart(MaxRow-2, hCol-1, h); MovePart(MaxRow-3, hCol, h); } void Diamond::Shape17(int hCol) { //**00 //*000 //*000 map[MaxRow-1][hCol]='*'; map[MaxRow-1][hCol+1]='*'; map[MaxRow-2][hCol]='*'; map[MaxRow-3][hCol]='*'; int h= GetHeight(MaxRow-4, hCol);// cout<< h< MovePart(MaxRow-4, hCol, h); MovePart(MaxRow-2, hCol+1, h); } void Diamond::Shape18(int hCol) { //*000 //***0 // 0000 map[MaxRow-1][hCol]='*'; map[MaxRow-2][hCol]='*'; map[MaxRow-2][hCol+1]='*'; map[MaxRow-2][hCol+2]='*'; int h= GetHeight(MaxRow-3, hCol);//cout<< h< for(int i=0; i<3; i++) MovePart(MaxRow-3, hCol+i, h); } /////////////////////////////////////////////////////////////////////// int Calc(const char map[][MaxCol], int outCmd[][2]); void PrintMap(const char map[][MaxCol]);//打印傳入的地圖 void PrintOutCmd(const int outCmd[][2], int n);//打印輸出方案，即選擇的模塊信息 int GetMin(const int a[], int len);//選擇所需的模塊數量較少的數據 int Project(const char map[][MaxCol], int out[][1000][2], int n); int ChangeCol(int choice, int hCol);//轉換列號，以滿足題目要求（原來是存儲的列號 //是地圖中具有最大高度的列號，現改為所選模塊的最左側有效方塊放到地圖中所在的列） 嗯···我學動歸不是很久，同樣是迷惘過，估計兩個月前剛剛開竅…… 你看他寫的什么無后效性什么最優子結構的就頭大，我也頭大%………… 動態規劃一般解決兩類問題，一類是最優化問題,就是問你最大價值最小數什么的，另一類是方案總數問題。 細分的話類型很多， 我見得多的（我是高二學生，目前在籌備NOIP） （你那題多我就只說名字了） 背包，樓上連9講都放上來了我就不多說了…… 最長不上升不下降子序列問題（比如說潘帕斯雄鷹生日模擬賽的飛翔，就是很經典的不下降的變形） 資源分配問題（比如說櫥窗布置，馬棚問題，機器分配問題） 區間動歸（乘積最大，能量項鏈等等） 最長公共子序列問題（有個遺傳編碼好像）； 解決方案樹的比如說爬樓梯問題…………………… 動態規劃的類型很多很多，因為他很靈活的，我們老師曾經給我們找了100個DP方程，但是那都沒有用，強記根本記不住，關鍵是理解。 深入一點的就有DP的優化，時間空間的降維（就是用別的方法去做，或者比如說背包本來是二維的空間優化過該成一維的了），樹形DP（這個我也不會）。 （優化里面有個很經典的題《過河》） 我對DP是屬于那種突然就開了竅的……別看說“動態規劃”什么的唬人，其實就是一個比較一個計算，知道他干什么了題上來就有頭緒，方程啊思想啊就有了…… 主要也是多看題吧，從簡單的開始，理解他的思想……自己寫動歸的時候注意下面幾個問題： 1、大前提是確定你做的是動歸題……看得多了也就知道自己面對的是什么類型的題了 2、次前提是想法要對（我做題的時候先想這道題時間空間的維度，然后根據這個去想方程），方程正確， 實在想不起來可以先看題解，去理解人家的思想之后，不要看標程把程序做出來…… 3、注意數組不要開的過小，一般都是左右都開大一點，比如他的數據范圍是1~100，數組就開0~101.這個是防越界的，因為很多DP賦初值的時候會用到F[0],F[0,0] 4、初始值要正確，因為很多DP其他地方都是正確的因為初始值賦錯了而全部過不了的情況是很常見的……（比如說USACO里面的貨幣系統） 5、DP循環的范圍要正確，一般根據題來判斷范圍寫多少的（比如說櫥窗問題，今天下午寫這個題因為循環寫錯了一直AC不了） USACO里也有很多DP題，可以做…… 以上全部手打，希望能對你有所幫助。 我也是正在學習的人，上面的東西不一定全部正確，但是對我而言很受用，也算是我的經驗了。希望日后能一起學習交流外加進步嘍 QQ：340131980 1.資源問題1 -----機器分配問題 F[I,j]:=max(f[i-1,k]+w[i,j-k]) 2.資源問題2 ------01背包問題 F[I,j]:=max(f[i-1,j-v]+w,f[i-1,j]); 3.線性動態規劃1 -----樸素最長非降子序列 F:=max{f[j]+1} 4.剖分問題1 -----石子合并 F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]); 5.剖分問題2 -----多邊形剖分 F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a); 6.剖分問題3 ------乘積最大 f[i,j]:=max(f[k,j-1]*mult[k,i]); 7.資源問題3 -----系統可靠性(完全背包) F[i,j]:=max{f[i-1,j-c*k]*P[I,x]} 8.貪心的動態規劃1 -----快餐問題 F[i,j,k]:=max{f[i-1,j',k']+(T-(j-j')*p1-(k-k')*p2) div p3} 9.貪心的動態規劃2 -----過河 f=min{{f(i-k)}(not stone) {f(i-k)}+1}(stone);+貪心壓縮狀態 10.剖分問題4 -----多邊形-討論的動態規劃 F[i,j]:=max{正正 f[I,k]*f[k+1,j]; 負負 g[I,k]*f[k+1,j]; 正負 g[I,k]*f[k+1,j]; 負正 f[I,k]*g[k+1,j];} g為min 11.樹型動態規劃1 -----加分二叉樹(從兩側到根結點模型) F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]} 12.樹型動態規劃2 -----選課(多叉樹轉二叉樹,自頂向下模型) F[I,j]表示以i為根節點選j門功課得到的最大學分 f[i,j]:=max{f[t.l,k]+f[t.r,j-k-1]+c} 13.計數問題1 -----砝碼稱重 f[f[0]+1]=f[j]+k*w[j]; (1<=i<=n; 1<=j<=f[0]; 1<=k<=a;) 14.遞推天地1 ------核電站問題 f[-1]:=1; f[0]:=1; f:=2*f[i-1]-f[i-1-m] 15.遞推天地2 ------數的劃分 f[i,j]:=f[i-j,j]+f[i-1,j-1]; 16.最大子矩陣1 -----一最大01子矩陣 f[i,j]:=min(f[i-1,j],v[i,j-1],v[i-1,j-1])+1; ans:=maxvalue(f); 17.判定性問題1 -----能否被4整除 g[1,0]:=true; g[1,1]:=false; g[1,2]:=false; g[1,3]:=false; g[i,j]:=g[i-1,k] and((k+a[i,p]) mod 4= j) 18.判定性問題2 -----能否被k整除 f[I,j±n mod k]:=f[i-1,j];-k<=j<=k; 1<=i<=n 20.線型動態規劃2 -----方塊消除游戲 f[i,i-1,0]:=0 f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k), f[i,p,k+len[j]]+f[p+1,j-1,0]} ans:=f[1,m,0] 21.線型動態規劃3 -----最長公共子串，LCS問題 f[i,j]={0(i=0)&(j=0); f[i-1,j-1]+1(i>0,j>0,x=y[j]); max{f[i,j-1]+f[i-1,j]}}(i>0,j>0,x<>y[j]); 22.最大子矩陣2 -----最大帶權01子矩陣O(n^2*m) 枚舉行的起始，壓縮進數列，求最大字段和，遇0則清零 23.資源問題4 -----裝箱問題(判定性01背包) f[j]:=(f[j] or f[j-v]); 24.數字三角形1 -----樸素の數字三角形 f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]); 25.數字三角形2 -----晴天小豬歷險記之Hill 同一階段上暴力動態規劃 if[i,j]:=min(f[i,j-1],f[I,j+1],f[i-1,j],f[i-1,j-1])+a[i,j] 26.雙向動態規劃1 數字三角形3 -----小胖辦證 f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j]) 27.數字三角形4 -----過河卒 //邊界初始化 f[i,j]:=f[i-1,j]+f[i,j-1]; 28.數字三角形5 -----樸素的打磚塊 f[i,j,k]:=max(f[i-1,j-k,p]+sum[i,k],f[i,j,k]); 29.數字三角形6 -----優化的打磚塊 f[I,j,k]:=max{g[i-1,j-k,k-1]+sum[I,k]} 30.線性動態規劃3 -----打鼴鼠’ f:=f[j]+1;(abs(x-x[j])+abs(y-y[j])<=t-t[j]) 31.樹形動態規劃3 -----貪吃的九頭龍 32.狀態壓縮動態規劃1 -----炮兵陣地 Max(f[Q*(r+1)+k],g[j]+num[k]) If(map and plan[k]=0) and ((plan[P] or plan[q]) and plan[k]=0) 33.遞推天地3 -----情書抄寫員 f:=f[i-1]+k*f[i-2] 34.遞推天地4 -----錯位排列 f:=(i-1)(f[i-2]+f[i-1]); f[n]:=n*f[n-1]+(-1)^(n-2); 35.遞推天地5 -----直線分平面最大區域數 f[n]:=f[n-1]+n :=n*(n+1) div 2+ 1; 36.遞推天地6 -----折線分平面最大區域數 f[n]:=(n-1)(2*n-1)+2*n; 37.遞推天地7 -----封閉曲線分平面最大區域數 f[n]:=f[n-1]+2*(n-1) :=sqr(n)-n+2; 38遞推天地8 -----凸多邊形分三角形方法數 f[n]:=C(2*n-2,n-1) div n; 對于k邊形 f[k]:=C(2*k-4,k-2) div(k-1);//(k>=3) 39遞推天地9 -----Catalan數列一般形式 1,1,2,5,14,42,132 f[n]:=C(2k,k) div(k+1); 40遞推天地10 -----彩燈布置 排列組合中的環形染色問題 f[n]:=f[n-1]*(m-2)+f[n-2]*(m-1);(f[1]:=m; f[2]:=m(m-1); 41線性動態規劃4 -----找數 線性掃描 sum:=f+g[j]; (if sum=Aim then getout; if sum 42線性動態規劃5 -----隱形的翅膀 min:=min{abs(w/w[j]-gold)}; if w/w[j] 43剖分問題5 -----最大獎勵 f:=max(f,f[j]+(sum[j]-sum)*i-t 44最短路1 -----Floyd f[i,j]:=max(f[i,j],f[i,k]+f[k,j]); ans[q[i,j,k]]:=ans[q[i,j,k]]+s[i,q[i,j,k]]*s[q[i,j,k],j]/s[i,j]; 45剖分問題6 -----小H的小屋 F[l,m,n]:=f[l-x,m-1,n-k]+S(x,k); 46計數問題2 -----隕石的秘密（排列組合中的計數問題） Ans[l1,l2,l3,D]:=f[l1+1,l2,l3,D+1]-f[l1+1,l2,l3,D]; F[l1,l2,l3,D]:=Sigma(f[o,p,q,d-1]*f[l1-o,l2-p,l3-q,d]); 47線性動態規劃 ------合唱隊形 兩次F:=max{f[j]+1}＋枚舉中央結點 48資源問題 ------明明的預算方案：加花的動態規劃 f[i,j]:=max(f[i,j],f[l,j-v-v[fb]-v[fa]]+v*p+v[fb]*p[fb]+v[fa]*p[fa]); 49資源問題 -----化工場裝箱員 50樹形動態規劃 -----聚會的快樂 f[i,2]:=max(f[i,0],f[i,1]); f[i,1]:=sigma(f[t^.son,0]); f[i,0]:=sigma(f[t^.son,3]); 51樹形動態規劃 -----皇宮看守 f[i,2]:=max(f[i,0],f[i,1]); f[i,1]:=sigma(f[t^.son,0]); f[i,0]:=sigma(f[t^.son,3]); 52遞推天地 -----盒子與球 f[i,1]:=1; f[i,j]:=j*(f[i-1,j-1]+f[i-1,j]); 53雙重動態規劃 -----有限的基因序列 f:=min{f[j]+1} g[c,i,j]:=(g[a,i,j] and g[b,i,j]) or(g[c,i,j]) 54最大子矩陣問題 -----居住空間 f[i,j,k]:=min(min(min(f[i-1,j,k],f[i,j-1,k]), min(f[i,j,k-1],f[i-1,j-1,k])), min(min(f[i-1,j,k-1],f[i,j-1,k-1]), f[i-1,j-1,k-1]))+1; 55線性動態規劃 ------日程安排 f:=max{f[j]}+P[I];(e[j] 56遞推天地 ------組合數 C[I,j]:=C[i-1,j]+C[I-1,j-1] C[I,0]:=1 57樹形動態規劃 -----有向樹k中值問題 F[I,r,k]:=max{max{f[l,I,j]+f[r,I,k-j-1]},f[f[l,r,j]+f[r,r,k-j]+w[I,r]]} 58樹形動態規劃 -----CTSC 2001選課 F[I,j]:=w(if i∈P)+f[l,k]+f[r,m-k](0≤k≤m)(if l<>0) 59線性動態規劃 -----多重歷史 f[i,j]:=sigma{f[i-k,j-1]}(if checked) 60背包問題(+-1背包問題+回溯) -----CEOI1998 Substract f[i,j]:=f[i-1,j-a] or f[i-1,j+a] 61線性動態規劃(字符串) -----NOI 2000古城之謎 f[i,1,1]:=min{f[i+length(s),2,1], f[i+length(s),1,1]+1}f[i,1,2]:=min{f[i+length(s),1,2]+words[s],f[i+length(s),1,2]+words[s]} 62線性動態規劃 -----最少單詞個數 f[i,j]:=max{f[I,j],f[u-1,j-1]+l} 63線型動態規劃 -----APIO2007數據備份 狀態壓縮＋剪掉每個階段j前j*2個狀態和j*2+200后的狀態貪心動態規劃 f:=min(g[i-2]+s,f[i-1]); 64樹形動態規劃 -----APIO2007風鈴 f:=f[l]+f[r]+{1(if c[l] g:=1(d[l]<>d[r]) 0(d[l]=d[r]) g[l]=g[r]=1 then Halt; 65地圖動態規劃 -----NOI 2005 adv19910 F[t,i,j]:=max{f[t-1,i-dx[d[[t]],j-dy[d[k]]]+1],f[t-1,i,j]; 66地圖動態規劃 -----優化的NOI 2005 adv19910 F[k,i,j]:=max{f[k-1,i,p]+1} j-b[k]<=p<=j; 67目標動態規劃 -----CEOI98 subtra F[I,j]:=f[I-1,j+a] or f[i-1,j-a] 68目標動態規劃 ----- Vijos 1037搭建雙塔問題 F[value,delta]:=g[value+a,delta+a] or g[value,delta-a] 69樹形動態規劃 -----有線電視網 f[i,p]:=max(f[i,p],f[i,p-q]+f[j,q]-map[i,j]) leaves>=p>=l, 1<=q<=p; 70地圖動態規劃 -----vijos某題 F[I,j]:=min(f[i-1,j-1],f[I,j-1],f[i-1,j]); 71最大子矩陣問題 -----最大字段和問題 f:=max(f[i-1]+b,b); f[1]:=b[1] 72最大子矩陣問題 -----最大子立方體問題 枚舉一組邊i的起始，壓縮進矩陣 B[I,j]+=a[x,I,j] 枚舉另外一組邊的其實，做最大子矩陣 73括號序列 -----線型動態規劃 f[I,j]:=min(f[I,j],f[i+1,j-1](ss[j]=”()”or(”[]”)), f[I+1,j+1]+1(s[j]=”(”or”[” ], f[I,j-1]+1(s[j]=”)”or”]”) 74棋盤切割 -----線型動態規劃 f[k,x1,y1,x2,y2]=min{min{f[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2], f[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2] min{}} 75概率動態規劃 -----聰聰和可可(NOI2005) x:=p[p[i,j],j] f[I,j]:=(f[x,b[j,k]]+f[x,j])/(l[j]+1)+1 f[I,i]=0 f[x,j]=1 76概率動態規劃 -----血緣關系 F[A, B]=(f[A0, B]+P[A1, B])/2 f[I,i]=1 f[I,j]=0(I,j無相同基因) 77線性動態規劃 -----決斗 F[I,j]=(f[I,j] and f[k,j]) and(e[I,k] or e[j,k]),i 78線性動態規劃 -----舞蹈家 F[x,y,k]=min(f[a[k],y,k+1]+w[x,a[k]],f[x,a[k],k+1]+w[y,a[k]]) 79線性動態規劃 -----積木游戲 F[I,a,b,k]=max(f[I,a+1,b,k],f[i+1,a+1,a+1,k’],f[I,a+1,a+1,k’]) 80樹形動態規劃（雙次記錄） -----NOI2003逃學的小孩 樸素的話枚舉節點i和離其最遠的兩個節點 j,k O(n^2) 每個節點記錄最大的兩個值，并記錄這最大值分別是從哪個相鄰節點傳過來的。當遍歷到某個孩子節點的時候，只需檢查最大值是否是從該孩子節點傳遞來的。如果是，就取次大，否則取最大值 81樹形動態規劃(完全二叉樹) -----NOI2006網絡收費 F[I,j,k]表示在點i所管轄的所有用戶中，有j個用戶為A，在I的每個祖先u上，如果N[a]>N則標0否則標1，用二進制狀態壓縮進k中，在這種情況下的最小花費 F[I,j,k]:=min{f[l,u,k and(s<<(i-1))]+w1,f[r,j-u,k and(s<<(i-1))]} 82樹形動態規劃 -----IOI2005河流 F:=max 83記憶化搜索 -----Vijos某題,忘了 F[pre,h,m]:=sigma{SDP(I,h+1,M+i)}(pre<=i<=M＋1) 84狀態壓縮動態規劃 -----APIO 2007動物園 f[I,k]:=f[i-1,k and not(1<<4)]+ NewAddVal 85樹形動態規劃 -----訪問術館 f[i,j-c×2]:= max( f[l,k], f[r,j-c×2-k]) 86字符串動態規劃 -----Ural 1002 Phone if exist(copy(s,j,i-j)) then f:=min(f,f[j]+1); 87多進程動態規劃 -----CEOI 2005 service Min( f[i,j,k], f[i-1,j,k]+ c[t[i-1],t]) Min( f[i,t[i-1],k], f[i-1,j,k]+ c[j,t]) Min( f[i,j,t[i-1]], f[i-1,j,k]+ c[k,t]) 88多進程動態規劃 -----Vijos1143三取方格數 max(f[i,j,k,l],f[i-1,j-R[m,1],k-R[m,2],l-R[m,3]]); if(j=k) and(k=l) then inc(f[i,j,k,l],a[j,i-j]) else if(j=k) then inc(f[i,j,k,l],a[j,i-j]+a[l,i-l]) else if(k=l) then inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]) else if(j=l) then inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]) else inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]+a[l,i-l]); 89線型動態規劃 -----IOI 2000郵局問題 f[i,j]:=min(f[I,j],f[k,j-1]+d[k+1,i]); 90線型動態規劃 -----Vijos 1198最佳課題選擇 if j-k>=0 then Min(f[i,j],f[i-1,j-k]+time(i,k)); 91背包問題 ----- USACO Raucous Rockers 多個背包，不可以重復放物品，但放物品的順序有限制。 F[I,j,k]表示決策到第i個物品、第j個背包，此背包花費了k的空間。 f[I,j,k]:=max(f[I-1,j,k],f[I-1,j,k-t]+p,f[i-1,j-1,maxtime-t]) 92多進程動態規劃 -----巡游加拿大（IOI95、USACO） d[i,j]=max{d[k,j]+1(a[k,i]& j f[i,j]表示從起點出發，一個人到達i，另一個人到達j時經過的城市數。d[i,j]=d[j,i]，所以我們限制i>j 分析狀態(i,j)，它可能是(k,j)(j 93動態規劃 -----ZOJ cheese f[i,j]:=f[i-kk*zl[u,1],j-kk*zl[u,2]]+a[i-kk*zl[u,1],j-kk*zl[u,2]] 94動態規劃 -----NOI 2004 berry線性 F[I,1]:=s F[I,j]:=max{min{s-s[l-1]},f[l-1,j-1]}(2≤j≤k, j≤l≤i) 95動態規劃 -----NOI 2004 berry完全無向圖 F[I,j]:=f[i-1,j] or(j≥w) and(f[i-1,j-w]) 96動態規劃 -----石子合并四邊形不等式優化 m[i,j]=max{m[i+1,j], m[i,j-1]}+t[i,j] 97動態規劃 -----CEOI 2005 service （k≥long，i≥1）g[i, j, k]=max{g[i-1,j,k-long]+1，g[i-1,j,k]} （k (0≤j≤m， 0≤k ans:=g[n,m,0]。 狀態優化：g[i, j]=min{g[i-1,j]，g[i-1,j-1]+long} 其中(a, b)+long=(a’, b’)的計算方法為： 當b+long≤t時： a’=a; b’=b+long; 當b+long＞t時： a’=a+1; b’=long; 規劃的邊界條件： 當0≤i≤n時，g[i,0]=(0,0) 98動態規劃 -----AHOI 2006寶庫通道 f[k]:=max{f[k-1]+x[k,j]-x[k,i-1], x[k,j]-x[k,i-1]} 99動態規劃 -----Travel A)費用最少的旅行計劃。 設f表示從起點到第i個旅店住宿一天的最小費用；g表示從起點到第i個旅店住宿一天，在滿足最小費用的前提下所需要的最少天數。那么： f=f[x]+v, g=g[x]+1 x滿足： 1、 x 2、對于所有的t< i, d– d[t]<= 800，都必須滿足： A. g[x]< g[t](f[x]= f[t]時) B. f[x]< f[t](其他情況) f[0]= 0，g[0]= 0。 Ans:=f[n+ 1]，g[n+1]。 B).天數最少的旅行計劃。 方法其實和第一問十分類似。 設g’表示從起點到第i個旅店住宿一天的最少天數；f’表示從起點到第i個旅店住宿一天，在滿足最小天數前提下所需要的最少費用。那么： g’= g’[x]+ 1, f’= f’[x]+ v x滿足： 1、 x 2、對于所有的t< i, d– d[t]<= 800，都必須滿足： f’[x]< f’[t] g’[x]= g’[t]時 g’[x]< g’[t]其他情況 f’[0]= 0，g’[0]= 0。 Ans:=f’[n+ 1]，g’[n+1]。 100動態規劃 -----NOI 2007 cash y:=f[j]/(a[j]*c[j]+b[j]); g:=c[j]*y*a+y*b; f:=max(f,g)二、編程! 方塊消除問題 動態規劃
三、200分求動態規劃詳解!!!