GCA

動態規劃經典教程 引言：本人在做過一些題目後對DP有些感想，就寫了這個總結： 第一節 動態規劃基本概念 一，動態規劃三要素：階段，狀態，決策。 他們的概唸到處都是，我就不多說了，我只說說我對他們的理解： 如果把動態規劃的求解過程看成一個工廠的生產線，階段就是生產某個商品的不同的環節，狀態就是工件當前的形態，決策就是對工件的操作。顯然不同階段是對產品的一個前面各個狀態的小結，有一個個的小結構成了最終的整個生產線。每個狀態間又有關聯（下一個狀態是由上一個狀態做了某個決策後產生的）。 下面舉個例子： 要生產一批雪糕，在這個過程中要分好多環節：購買牛奶，對牛奶提純處理，放入工廠加工，加工後的商品要包裝，包裝後就去銷售……，這樣沒個環節就可以看做是一個階段；產品在不同的時候有不同的狀態，剛開始時只是白白的牛奶，進入生產後做成了各種造型，從冷凍庫拿出來後就變成雪糕（由液態變成固態=_=||）。每個形態就是一個狀態，那從液態變成固態經過了冰凍這一操作，這個操作就是一個決策。 一個狀態經過一個決策變成了另外一個狀態，這個過程就是狀態轉移，用來描述狀態轉移的方程就是狀態轉移方程。 經過這個例子相信大家對動態規劃有所瞭解了吧。 下面在說說我對動態規劃的另外一個理解： 用圖論知識理解動態規劃：把動態規劃中的狀態抽象成一個點，在有直接關聯的狀態間連一條有向邊，狀態轉移的代價就是邊上的權。這樣就形成了一個有向無環圖AOE網（為什麼無環呢？往下看）。對這個圖進行拓撲排序，刪除一個邊後同時出現入度為0的狀態在同一階段。這樣對圖求最優路徑就是動態規劃問題的求解。 二，動態規劃的適用範圍 動態規劃用於解決多階段決策最優化問題，但是不是所有的最優化問題都可以用動態規劃解答呢？ 一般在題目中出現求最優解的問題就要考慮動態規劃了，但是否可以用還要滿足兩個條件： 最優子結構（最優化原理） 無後效性 最優化原理在下面的最短路徑問題中有詳細的解答； 什麼是無後效性呢？ 就是說在狀態i求解時用到狀態j而狀態j就解有用到狀態k…..狀態N。 而求狀態N時有用到了狀態i這樣求解狀態的過程形成了環就沒法用動態規劃解答了，這也是上面用圖論理解動態規劃中形成的圖無環的原因。 也就是說當前狀態是前面狀態的完美總結，現在與過去無關。。。 當然，有是換一個劃分狀態或階段的方法就滿足無後效性了，這樣的問題仍然可以用動態規劃解。 三...

鎮上有 N 個人，照一句諺語說：「我朋友們的朋友也是我的朋友」。A 和 B 為朋友，B 和 C 為朋友，所以 C 和 A 也為朋友。 讀入 N 和 M 兩整數，N 為鎮上有公民 1 - N，而接下來會有 M 列資料，M 列資料都有兩整數 a, b，代表公民 a 和公民 b 為朋友。最後請你算出這鎮上最大朋友群的數量為多少。 其實只要給朋友群定義一個朋友群編號，如果雙方都沒有朋友群編號，就將兩人都定義一個新的朋友群編號，並將此朋友編號數量變成 2；若兩人其中一人沒有朋友群編號，則將他加入有編號的朋友群之中；如果兩人都有朋友群編號，就將其中一方的所有朋友的編號改為另一方的編號，順便將另一方朋友編號數量累加對方的數量。 一開始宣告陣列以及初始化朋友群編號以及朋友群數量：

解法 若一圖形為tree的結構，表示此圖形中所有的點都互相連通且必無cycle存在，因此判斷cycle的存在是本題最重要的關鍵。一個判斷有無cycle存在的簡單方法是利用集合的概念，把目前已知的連線關係歸類到同一個集合中，我們設計一個範例來逐步解釋這個過程： Input 1 2 2 3 4 6 2 5 2 4 5 6 0 0 首先我們假設所有的點都不在任何一個集合中。 第一個輸入：1 2，代表1指向2，所以我們把1與2歸類成集合I。 第二個輸入：2 3，表示2指向3，所以3也屬於集合I。 第三個輸入：4 6，表示4指向6，所以4與6屬於另一個集合II 下一個輸入：2 5，所以5也屬於集合I。 下一個輸入：2 4，所以包含4的這個集合內的全部元素都應該歸類到集合I。 最後一個輸入：5 6，表示5指向6，但是5與6已經屬於同一個集合，將同一個集合內的兩個點連起來必然會形成cycle，因此這個圖形不是tree。 若所有的輸入處理完後，所有的點都屬於同一個集合，則這個圖形就是一個tree。

題目大意： 有k個好人跟k個壞人按順序坐著，然後按第m個殺人，求出把壞人全部先殺光的m的最小值。 0<k<14。典型的約瑟環問題。 解題思路： 一開始看見數據量那麼小，還以為暴力一定可以出來，結果，好吧，當k為0以上時，時間大得驚人，自己暴力的方法還是有很大問題啊。 比較標準的做法是：在這麼多個人中，始終用start跟end來確定好人那個序列的位置。 比如一開始是1 2 3 4 5 6，那麼start = 0,end = 3(從0開始計數)當m等於5的時候，kill後就剩下1 2 3 4 6 ，重新拍下序列變成 6 1 2 3 4 ，這時候 start = ((start-m)%n+n)%n; end = ((end-m)%n+n)%n; n是當前剩下的人數。定完位置之後，kill的位置為kill = (m-1)%n; 這樣就可以做了。 代碼： #include using namespace std; bool joseph(int k, int m) { int start = 0, end = k - 1; //定位，定好人的位置 int kill;//殺人的序號 for(int n = 2 * k; n > k; n--) //n代表人數 { kill = (m - 1) % n; if(kill >= start && kill <= end) { return false; } start = ((start - m) % n + n) % n;//定位，加n模n是為了防止負數 end = ((end - m) % n + n) % n; } return true; } int main(void) { int f[14]; for(int i = 1; i < 14; i++) for(int j =...

The Problem The square field consists of M×M cells. Each cell is colored in one of three colors (1,2,3). The initial state is chosen in one of the cells of color 1. In each step one allowed to move one cell up, down, left or right remaining inside the field. You are to define the minimal amount of steps one should make to get a cell of color 3 independent on the initial state. Note that the field contains at least one cell of color 1 and at least one cell of color 3. The Input The input consists of several input blocks. The first line of each block contains integer M, the size of the field. Then there are M lines with colors of the cells. The Output For each input block the output should consist of one line with the integer, the minimal amount of steps one should make to get a cell of color 3 independent on the initial state. Sample Input 4 1223 2123 2213 3212 2 12 33 Sample Output 3 1

Problem 1. 搭帳篷 (Time Limit: 20 seconds) 問題敘述 : 露營時都搭過帳棚吧？但帳棚也不是說搭就搭，必須要有一塊平坦的空地才行， 否則就必須要先整理場地，清除石塊、雜物才能搭好。但也不是說清理就清理， 有時候如果出現很大塊的石頭或是大型的坑洞，帳篷就不得不避開這樣的地方。 假設營地為一個的 M × N 矩形，並分為M × N 個方格，每個方格為場地的最小 單位，方格上的數字分別為整數0,1,或2，分別代表場地的情形。數字0 代表該 方格的空地可直接使用，並且每個單位需要5 塊錢。數字1 代表該方格的空地經 過整理過後即可使用，由於需要清理費，因此每個單位收10 塊錢。數字2 代表 該方格的空地是無法清理的障礙物，不可搭帳篷。限制所搭帳篷的形狀必須都是 “正方形”。如今你身上有一筆錢準備用來搭帳篷，請你求出在這個營區上，符 合你預算內能夠搭建帳篷的最大面積單位? 輸入說明 : 輸入含多筆測資，每筆測資的第一行為三個正整數 M,N( 1 , 100MN )以及 P( 0 100000P ) 數字間有一個空格符號，代表該營區為 MN 的矩形以及你 目前有P 塊錢。接下來有M 行，每行有N 個數字(數字為0~2 之間的整數，兩個 數字間有一個空格符號)，分別代表該營區的場地情形。若每筆測資第一行的三 個整數皆為0，即代表測資結束。 輸出說明 : 對於每筆測資，輸出該營區在符合你預算內能夠搭建帳篷的最大面積單位。每筆 測資答案輸出於一行。

UVA 10003 Cutting Sticks 本題吧，經典的DP。本菜鳥第一次寫解題報告，以前的題都沒好意思寫。求高手別噴。 題目意思應該還是很明白的。就是一根木頭，告訴你多長，要切幾下，分別切在哪些個點。然後呢，切一根多長的木頭，就要多少錢。然後求一個最便宜的切木有的方案。 這個題目是跟白書配套的，看過那個9.4的最優矩陣鏈乘的話，就能夠想到，其實這個題思路跟那個矩陣鏈乘一樣的。 核心的東西就是這個方程：dp(i,j)=min{dp(i,k)+dp(k,j)+c[j]-c[i]}（其中（i<k<j)，k也就是切斷第i個點跟第j個點之間的那段木頭的那個點） 最後稍注意一下邊界的條件，當i+1=j的時候，就是已經切到極限的時候，dp(i,j)顯然是0。 依樣畫葫蘆吧，用記憶化搜索寫了一遍。 View Code 1 #include 2 using namespace std; 3 #define MAX 0xffffff 4 int d[60][60],c[60]; 5 int dp(int i,int j) 6 { 7 int &ans = d[i][j]; 8 if(ans != -1) return ans; 9 else if(i + 1 == j) 10 { 11 ans = 0; 12 return ans; 13 } 14 else 15 { 16 ans = MAX; 17 int temp,k; 18 for(k = i + 1;k < j;k++) 19 { 20 temp = dp(i,k) + dp(k,j) + c[j] - c[i]; 21 if(temp >len) 30 { 31 if(len == 0) 32 break; 33 cin>>points; 34 c[0] = 0; 35 c[points + 1] = len; 36 int i,j; 37 ...