1、習題選講2011-12-292第六章1011 Lennys Lucky Lotto1121 Tri Tiling1264 Atomic Car Race1828 Minimal1527 Tiling a Grid With Dominoes1148 過河1176 Two Ends1163 Tour1345 能量項鏈1687 Permutation2011-12-2931011 Lennys Lucky Lotto題目大意：給出N和M，問有多少個長度為N的序列，使得每個數的范圍都在1,M之間，并且序列中每一個數至少是前一個數的兩倍。2011-12-2941011 Lennys Lucky Lot

2、to解題思路：dpij表示考慮前i位且第i位為j的方案。dpij=sumdpi-1k | 1=k=j/2先枚舉位數i，再枚舉最后一個數j，最后統計k。時間復雜度O(N*M*M)。2011-12-2951011 Lennys Lucky Lottofor (j=1;j=2000;j+)dp1j=1;for (i=2;i=10;i+) for (j=1;j=2000;j+) dpij=0;for (k=1;k*2 51 - 32 - 43 - 52 - 52011-12-2991121 Tri Tiling狀態轉移：5 - 35 - 25 - 04 - 23 - 52011-12-29101121

3、 Tri Tiling初始第0列是狀態0，終止第n+1列是狀態5。dp00=1;for (i=1;i=n+1;i+) dpi5+=dpi-10;dpi3+=dpi-11;dpi4+=dpi-12;dpi5+=dpi-12;dpi1+=dpi-13;dpi5+=dpi-13;dpi2+=dpi-14;dpi3+=dpi-15;dpi2+=dpi-15;dpi0+=dpi-15;2011-12-29111264 Atomic Car Race題目大意：在一次賽車比賽中，在檢查點換輪胎需要花費一定時間，而速度與離上一次換輪胎的路程相關，問從起點到終點的最少時間。2011-12-29121264 At

4、omic Car Race解題思路：先求出從換完輪胎到走每個距離段所用的時間。d0=0;for (i=0;ian;i+)if (ir)temp=1/(v-f*(r-i);elsetemp=1/(v-e*(i-r);di+1=di+temp;2011-12-29131264 Atomic Car Race再給出每兩個檢查點（包括起點）之間的用時。for (i=0;in;i+)for (j=i+1;j=n;j+)cij=daj-ai;2011-12-29141264 Atomic Car Race再用遞歸的方法進行動態規劃。dpij=mincij,dpik+dpkj+b | ikj2011-12-

5、29151264 Atomic Car Racedouble cal(int s,int t) if (visitedst)return dpst;visitedst=true;dpst=cst;for (int i=s+1;it;i+) double temp=cal(s,i)+cal(i,t)+b;if (tempdpst)dpst=temp;return dpst;2011-12-29161828 Minimal題目大意：給出兩個集合S1，S2，在S2中選出一些不重復的數與S1每個數匹配，使得匹配的數的差的絕對值盡量小。集合中數的個數不超過500。2011-12-29171828 Min

6、imal解題思路：首先證明，在S1中取兩個數a1,b1，在S2中取兩個數a2,b2，若a1b1,a2b2，則|a1-a2|+|b1-b2|a1-b2|+|a2-b1|。即對于已排序的S1的數，只會按順序對應已排序的S2的數。dpij表示S1中前i個數與S2中前j個數匹配時，第i個數或之前的匹配數值差的絕對值之和。2011-12-29181828 Minimalsort(s1,s1+n);sort(s2,s2+m);dp00=abs(s10-s20);for (i=1;im;i+) dp0i=min(dp0i-1,abs(s10-s2i); for (i=1;in;i+) dpii=dpi-1i

7、-1+abs(s1i-s2i); for (j=i+1;j1, 0-2, 0-3, 0-5, 1-2, 1-0, 2-1, 2-0, 3-0, 3-4, 4-3, 5-0, 0-02011-12-29211527 Tiling a Grid With Dominoesdp00=1;for (i=1;i=n+1;i+) dpi0+=dpi-10;dpi1+=dpi-10;dpi2+=dpi-10;dpi3+=dpi-10;dpi5+=dpi-10;dpi2+=dpi-11;dpi0+=dpi-11;dpi1+=dpi-12;dpi0+=dpi-12;dpi0+=dpi-13;dpi4+=dpi-

8、13;dpi3+=dpi-14;dpi0+=dpi-15;2011-12-29221148 過河題目大意：橋的起點為0，終點為L，其中地有M個石子。青蛙每次跳的范圍為S,T，問要跳過橋最小踩到石子次數。1 = L = 1091 = S = T = 101 = M = 1002011-12-29231148 過河解題思路：L的值大太，直接按L的值進行動態規劃不可行。分情況：若S和T相等，則踩到的石子數是固定的；若S和T不相等，因為S和T的最大值為10，所以當兩個石子相差太遠是沒有意義的，這里取的值為90，當石子距離相差90以上時，看作90，答案不變。壓縮后橋長度不超過10000，直接動態規劃即可

9、。2011-12-29241148 過河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();2011-12-29251148 過河void work() L=rockm+90;for(i=s;i=L;i+) max=101;for(j=i-t;j=0)if(fj&dpj+dpimax) max=dpj+dpi;fi=1;dpi=max;2011-12-29261176 Two Ends題目大意：兩個人輪流從一列數中取數，只能從兩端取。第一個人可以用任意策

10、略，第二個人貪心每次取最大的數。一個人的分數等于他取的數的總和。問分數差值最大為多少。nr) return 0; if (visitedlr) return dplr; visitedlr=true; if (r-l+1)%2=1) if (al=ar) return dplr=cal(l+1,r)-al; else return dplr=cal(l,r-1)-ar; else return dplr=max(cal(l+1,r)+al,cal(l,r-1)+ar);2011-12-29291163 Tour題目大意：有一個人要從起點開始經過所有目的地再回到起點。他只能從起點（最左端的點），

11、向右一直到達最右端的點，再返回起點，在這一次往返要經過所有的點。求最短路程。2011-12-29301163 Tour解題思路：一次往返可以看作從最左端點到最右端點的兩條獨立路徑。對所有點按從左到右排序后，用dpij表示兩條路徑現在分別在i和j點。假設ij，則現在輪到枚舉第i+1個點，則可以從i到達第i+1個點，也可以j到達第i+1個點。2011-12-29311163 Tourfor (i=0;in-1;i+) for (j=0;jj) if (i-1j) dpij=dpi-1j+di-1i; else for (k=0;kj;k+) temp=dpkj+dki; if (dpijtemp)

12、 dpij=temp; else if (ji) /* similar to (ij) */ 2011-12-29321345 能量項鏈題目大意：給出一串項鏈，每次可以選相鄰兩個珠子進行聚合，釋放出一定的能量，并產生一個新珠子。項鏈是頭尾相接的。求釋放的能量的總和的最大值。項鏈長度不超過100。2011-12-29331345 能量項鏈解題思路：每次聚合，都會使數字中一的個數字消失。動態規劃，狀態為i,j表示從i開始，按順時針方向到j，這一段珠子所聚合得到的能量最大值。狀態轉移，要求出i,j的值，則存在一個k在i和j之間，i,j的值為i,k的值與k+1,j的值與這次聚合所釋放出的能量的總和，取

13、最大值。且長度較大的區間需要長度較小的區間得到，因此枚舉順序為區間的長度從小到大。2011-12-29341345 能量項鏈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; 2011-12-29351687 Permutation題目大意：n個數的排列，可以在中間插入小于號和大于號，如1 3 5 4 2 變成 1342。現在問n個數其中有k個小于號的排列有多少個。n,k=1002011-12-29361687 Permutation解題思路：用dpij表示i個數的排列有j個小于號，現在要擴展到i+1個數的排列，即插入一個數要大于當前所有數。