算法分析習題課 第六章

1、算法分析習題選講(第六章)第六章1011 Lennys Lucky Lotto1121 Tri Tiling1264 Atomic Car Race1828 Minimal1527 Tiling a Grid With Dominoes1148 過河1176 Two Ends1163 Tour1345 能量項鏈1687 Permutation1011 Lennys Lucky Lotto給出N和M，問有多少個長度為N的序列，使得每個數(shù)的范圍都在1,M之間，并且序列中每一個數(shù)至少是前一個數(shù)的兩倍。解題思路dpij表示考慮前i位且第i位為j的方案。先枚舉位數(shù)i，再枚舉最后一個數(shù)j，最后統(tǒng)計k。時間

2、復雜度O(N*M*M)。1121 Tri Tiling用1*2的長方形鋪滿3*n的長方形，有多少種方法。解題思路定義如圖幾種缺口狀態(tài)。012345狀態(tài)轉(zhuǎn)移0 - 51 - 32 - 43 - 52 - 55 - 35 - 25 - 04 - 23 - 5初始第0列是狀態(tài)0終止第n+1列是狀態(tài)51264 Atomic Car Race在一次賽車比賽中，在檢查點換輪胎需要花費一定時間，而速度與離上一次換輪胎的路程相關(guān)，問從起點到終點的最少時間。解題思路先求出從換完輪胎到走每個距離段所用的時間dpij表示到達第i個換輪胎點，上一次換輪胎位置是j時的消耗值初始狀態(tài)有dp10, dp11答案為 dpnn

3、 b（假設(shè)在最后一個位置換輪胎，但這一次換輪胎是沒必要的）1828 Minimal給出兩個集合S1，S2，在S2中選出一些不重復的數(shù)與S1每個數(shù)匹配，使得匹配的數(shù)的差的絕對值盡量小。集合中數(shù)的個數(shù)不超過500。解題思路首先證明，在S1中取兩個數(shù)a1,b1，在S2中取兩個數(shù)a2,b2，若a1b1,a2b2，則|a1-a2|+|b1-b2|1, 0-2, 0-3, 0-5, 1-2, 1-0, 2-1, 2-0, 3-0, 3-4, 4-3, 5-0, 0-01148 過河橋的起點為0，終點為L，其中地有M個石子。青蛙每次跳的范圍為S,T，問要跳過橋最小踩到石子次數(shù)。1 = L = 1091 =

4、S = T = 101 = M = 100解題思路L的值大太，直接按L的值進行動態(tài)規(guī)劃不可行。分情況：若S和T相等，則踩到的石子數(shù)是固定的；若S和T不相等，因為S和T的最大值為10，所以當兩個石子相差太遠是沒有意義的，這里取的值為90，當石子距離相差90以上時，看作90，答案不變。壓縮后橋長度不超過10000，直接動態(tài)規(guī)劃即可。for(i=0;i90)deltai=90;for(i=1;i=m;i+)rocki=rocki-1+deltai-1;for(i=1;i=m;i+)dprocki=1;f0=1;work();void work() L=rockm+90;for(i=s;i=L;i+)

5、 max=101;for(j=i-t;j=0)if(fj&dpj+dpimax) max=dpj+dpi;fi=1;dpi=max;1176 Two Ends兩個人輪流從一列數(shù)中取數(shù)，只能從兩端取。第一個人可以用任意策略，第二個人貪心每次取最大的數(shù)。一個人的分數(shù)等于他取的數(shù)的總和。問分數(shù)差值最大為多少。n=dataj) fij=-datai+fi+1j; else fij=-dataj+fij-1;for(i=0;i=0;i-)for(j=i+1;j=dataj) fij=-datai+fi+1j; else fij=-dataj+fij-1;else fij=max(datai+fi+1j,

6、dataj+fij-1);1163 Tour有一個人要從起點開始經(jīng)過所有目的地再回到起點。他只能從起點（最左端的點），向右一直到達最右端的點，再返回起點，在這一次往返要經(jīng)過所有的點。求最短路程。解題思路一次往返可以看作從最左端點到最右端點的兩條獨立路徑。對所有點按從左到右排序后，用dpij表示兩條路徑現(xiàn)在分別在i和j點。假設(shè)ij，則現(xiàn)在輪到枚舉第i+1個點，則可以從i到達第i+1個點，也可以j到達第i+1個點。1345 能量項鏈給出一串項鏈，每次可以選相鄰兩個珠子進行聚合，釋放出一定的能量，并產(chǎn)生一個新珠子。項鏈是頭尾相接的。求釋放的能量的總和的最大值。項鏈長度不超過100。解題思路每次聚合，

7、都會使數(shù)字中一的個數(shù)字消失。動態(tài)規(guī)劃，狀態(tài)為i,j表示從i開始，按順時針方向到j(luò)，這一段珠子所聚合得到的能量最大值。狀態(tài)轉(zhuǎn)移，要求出i,j的值，則存在一個k在i和j之間，i,j的值為i,k的值與k+1,j的值與這次聚合所釋放出的能量的總和，取最大值。且長度較大的區(qū)間需要長度較小的區(qū)間得到，因此枚舉順序為區(qū)間的長度從小到大。for (step=1;stepn;step+) for (i=0;i=n*2) break; for (k=i;kj;k+) temp=ansik+ansk+1j +ai*ak+1*aj+1; if (ansijtemp) ansij=temp; 1687 Permutationn個數(shù)的排列，可以在中間插入小于號和大于號，如1 3 5 4 2 變成 1342?，F(xiàn)在問n個數(shù)其中有k個小于號的排列有多少個。n,k=100解題思路用d