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

#include <stdio.h> #include <stdlib.h> #include <math.h> int prime(int p){ int i; for(i=2;i<=sqrt(p);i++){ if(p%i==0)return 0; } return 1; } int main(int argc, char *argv[]) { int i,j,stack[2000],n,c,k; while(scanf("%d%d",&n,&c)!=EOF){ for(i=1,j=0;i<=n;i++){ if(prime(i))stack[j++]=i; } printf("%d %d:",n,c); if(2*c>=j ||2*c-1>=j)for(i=0;i<j;i++)printf(" %d",stack[i]); else if(j%2==0){ for(i=j/2-c;i<=j/2+c-1;i++){ printf(" %d",stack[i]); } } else if(j%2==1){ for(i=j/2-c+1;i<=j/2+c-1;i++){ printf(" %d",stack[i]); } } printf("\n\n"); } return 0; }

有一項決策要投票表決，一人一票，不得投廢票，過半數贊成則通過，反之則否決。投票者有許多派系組成，各個派系都相當團結，同樣派系的人，要嘛全部 都是投贊成票，要嘛全部都是投反對票。然而有些派系人多，有些派系人少，人多的派系能左右大局，人少的派系卻勢單力薄。於是產生一個問題：有能力對最終決 策造成影響的是哪些派系？影響能力又是多少？ 一個派系有能力對決策造成影響，是指所有派系都設定立場之後，此派系一旦改變立場，會馬上顛倒決策結果。換個角度來說，是指此派系之外的所有派系都投完票之後，此派系若全數投贊成票，則會使決策順利通過，反之若全數投反對票，則會使決策無法通過。 Banzhaf Power Index 的計算方式是這樣的：一個派系 X 的 Banzhaf Power Index = 派系 X 影響決策的情況數目 ÷ ( 派系 1 影響決策的情況數目 + ... + 派系 N 影響決策的情況數目 ) 。所有派系的 Banzhaf Power Index 的總和會是 1 。 藉由 Banzhaf Power Index ，可以看出各派系的實力，也可以看出投票表決是否公平。 1. A派系9票、B派系9票、C派系7票、D派系3票、E派系1票、F派系1票。 總共投票數為30票。過半數之票數為16票。 2. 以A派系為例，A派系影響決策的情況，一共有16種： AB AC ABC ABD ABE ABF ACD ACE ACF ABDE ABDF ABEF ACDE ACDF ACEF ADEF 派系有出現，表示投贊成票；派系無出現，表示投反對票。 拿掉A則會逆轉決策結果。 3. 可以發現D派系、E派系、F派系， 完全無法介入結果，沒有任何影響力： | votes | power | BPI --+-------+-------+------- A | 9 | 16 | 16/48 B | 9 | 16 | 16/48 C | 7 | 16 | 16/48 D | 3 | 0 | 0 E | 1 | 0 | 0 F | 1 | 0 | 0 --+-------+-------+-------- | 30 | 48 | 1.0 int w[6]; 

Money Changing Problem 的各種延伸問題   能否湊得某個價位（ Money Changing Problem ） int price[5] = {5, 2, 6, 11, 17};   // 各種面額，順序可隨意。 bool c[1000+1]; // 看看 {5, 2, 6, 11, 17} 這些面額湊不湊得到價位 m void change(int m) {     memset(c, false, sizeof(c));     c[0] = true;     for (int i = 0; i < 5; ++i)             // 依序加入各種面額         for (int j = price[i]; j <= m; ++j) // 由低價位逐步到高價位             c[j] ||= c[j-price[i]];         // 湊、湊、湊     if (c[m])         cout << "湊得到";     else         cout << "湊不到"; } int price[5] = {5, 2, 6, 11, 17}; int c[5][1000+1];   // 大於等於0代表該問題有計算過，-1代表沒計算過。                     // 一開始必須全部初始化為-1。 void change(int n, int m) {     if (n < 0 || m < 0) return 0;   // 0 代表 false     if (m == 0) return 1;           // 1 代表 true     if (c[n][m] != -1) return c[n][m];     return c[n][m] = change(n-1, m) | change(n, m - price[n]); } 湊得某個價位的湊法共有幾種（ Coin Change Problem ） int price[5] = {5, 2, 6, 11, 17};

讓背包裡面的物品總價值最大 const int N = 100, W = 100000; int cost[N], weight[N]; int c[W + 1];   // 只需要一條陣列就夠了 void knapsack(int n, int w) {     memset(c, 0, sizeof(c));     for (int i = 0; i < n; ++i)         for (int j = w; j - weight[i] >= 0; --j)    // 由後往前             c[j] = max(c[j], c[j - weight[i]] + cost[i]);     cout << "最高的價值為" << c[w]; }

計算 LCS 的長度 // 為了實作方便，從陣列的第1格開始存入序列。 int s1[7+1] = {0, 2, 5, 7, 9, 3, 1, 2}; int s2[5+1] = {0, 3, 5, 3, 2, 8}; // DP 的表格 int array[7+1][5+1]; void LCS() {     將 array[x][0] 和 array[0][x] 都設為 0 ;     for (int i = 1; i <= s1_length; i++)         for (int j = 1; j <= s2_length; j++)             if (s1[i] == s2[j])                 // 這裡加上的 1 是指 e1 的長度為 1                 array[i][j] = array[i-1][j-1] + 1;             else                 array[i][j] = max(array[i-1][j], array[i][j-1]);     cout << "LCS 的長度是" << array[seq1_length][seq2_length]; } 找出一個 LCS // 為了實作方便，從陣列的第1格開始存入序列。 int s1[7+1] = {0, 2, 5, 7, 9, 3, 1, 2}; int s2[5+1] = {0, 3, 5, 3, 2, 8}; // DP 的表格 int array[7+1][5+1]; // 記錄這一格的最大值是從哪一格求得的 int prev[7+1][5+1]; void LCS() {     將 array[x][0] 和 array[0][x] 都設為 0 ;     for (int i = 1; i <= s1_length; i++)         for (int j = 1; j <= s2_length; j++)             if (s1[i] == s2[j])

計算 LIS 的長度 int s[5];       // 用來存 sequence int array[5];   // 第 x 格的值為 sequence: s[0]~s[x] 的 LIS 長度 int LIS() {     // 初始化，每一個數字本身就是長度為一的 subsequence     for (int i=0; i<5; i++) array[i] = 1;     // LIS     for (int i=0; i<5; i++)         for (int j=i+1; j<5; j++)   // 找出能接在 s[i] 後面的數字             if (s[j] > s[i])        // 若是可以接，長度就增加                 array[j] = max(array[j], array[i] + 1);     // array 中最大的值即為 LIS 的長度     int ans = 0;     for (int i=0; i<5; i++)         ans = max(ans, array[i]);     return ans; } 找出一個 LIS int s[5]; int array[5]; int prev[5];    // prev[x] 紀錄 s[x] 是接在哪個位置的數字後面                 // 如果它前面沒有數字就紀錄 -1 int LIS() {     for (int i=0; i<5; i++) array[i] = 1;     // -1 代表這個數字沒有接在其他數字之後     for (int i=0; i<5; i++) prev[i] = -1;     for (int i=0; i<5; i++)         for (int j=i+1; j<5; j++)             if (s[j] > s[i])                 if (array[i] + 1 > array[j])         

/* 首先我想說明幾點問題。 你給的信息太少了，所以我只能自己假定某些條件，然後去實現程序。 1.我是在原來的程序上稍微改動了一下。 2.程序中的路徑這次設為單項的,graph[i][j]表示從i到j有一條路徑，而不能表示從j到i 也有一條路徑。這點要注意 3.設定矩陣中只有0和1,1表示有一條路徑，0表示沒有路徑 4.設定該程序的輸入格式為：首先輸入一個n表示一共有n個節點；然後輸入n*n的矩陣； 最後輸入兩個數x,y(1<=x,y<=n)，表示求x, y這兩點之間的所有路徑。 */ #include <stdio.h> #include <math.h> int graph[100][100];///graph[i][j]為0表示i, j兩點之間不通，為1表示有一條路 int stack[120], m=1, n, x, y;///存儲路徑 void dfs(int p) { int i, j; for(i=1; i<=n; i++) { if(graph[p][i]==1) { if(i == y)///如果深搜到了終點，就輸出剛才經過的路徑 { for(j=0; j<m; j++) { printf("%-5d", stack[j]); } printf("%-5d\n", y); } else///如果該點不是終點 { graph[p][i] = 0; stack[m] = i;///將該點存起來 m++; dfs(i);///接著深搜 graph[p][i] = 1; m--; } } } }

struct Point {double x, y;} p[10]; // 十個頂點的多邊形 bool point_in_polygon(Point& t) { bool c = false; for (int i = 0, j = 10-1; i t.y) != (p[j].y > t.y) && t.x < (p[j].x-p[i].x)*(t.y-p[i].y)/(p[j].y-p[i].y)+p[i].x) c = !c; return c; }