[學習]算法分析與設(shè)計課件：習題選講第六章bywxyz

1、習題選講,趙浩泉wxyz202@soj.me,2011-12-29,2,第六章,1011 Lenny's Lucky Lotto1121 Tri Tiling1264 Atomic Car Race1828 Minimal1527 Tiling a Grid With Dominoes1148 過河1176 Two Ends1163 Tour1345 能量項鏈1687 Permutation,2011-12-

2、29,3,1011 Lenny's Lucky Lotto,題目大意：給出N和M，問有多少個長度為N的序列，使得每個數(shù)的范圍都在[1,M]之間，并且序列中每一個數(shù)至少是前一個數(shù)的兩倍。,2011-12-29,4,1011 Lenny's Lucky Lotto,解題思路：dp[i][j]表示考慮前i位且第i位為j的方案。dp[i][j]=sum{dp[i-1][k] | 1<=k<=j/2}先枚舉位數(shù)

3、i，再枚舉最后一個數(shù)j，最后統(tǒng)計k。時間復雜度O(N*M*M)。,2011-12-29,5,1011 Lenny's Lucky Lotto,for (j=1;j<=2000;j++)dp[1][j]=1;for (i=2;i<=10;i++) {for (j=1;j<=2000;j++) {dp[i][j]=0;for (k=1;k*2<=j;k++)dp[i][j]+=

4、dp[i-1][k];}},2011-12-29,6,1121 Tri Tiling,題目大意：用1*2的長方形鋪滿3*n的長方形，有多少種方法。,2011-12-29,7,1121 Tri Tiling,解題思路：定義如圖幾種缺口狀態(tài)。,0,1,2,3,4,5,,,,,,,,,,,,,,,,,,,2011-12-29,8,1121 Tri Tiling,狀態(tài)轉(zhuǎn)移：,2011-12-29,9,1121 Tri Tiling,狀

5、態(tài)轉(zhuǎn)移：,2011-12-29,10,1121 Tri Tiling,初始第0列是狀態(tài)0，終止第n+1列是狀態(tài)5。dp[0][0]=1;for (i=1;i<=n+1;i++) {dp[i][5]+=dp[i-1][0];dp[i][3]+=dp[i-1][1];dp[i][4]+=dp[i-1][2];dp[i][5]+=dp[i-1][2];dp[i][1]+=dp[i-1][3];dp[i][5]

6、+=dp[i-1][3];dp[i][2]+=dp[i-1][4];dp[i][3]+=dp[i-1][5];dp[i][2]+=dp[i-1][5];dp[i][0]+=dp[i-1][5];},2011-12-29,11,1264 Atomic Car Race,題目大意：在一次賽車比賽中，在檢查點換輪胎需要花費一定時間，而速度與離上一次換輪胎的路程相關(guān)，問從起點到終點的最少時間。,2011-12-29,12,1

7、264 Atomic Car Race,解題思路：先求出從換完輪胎到走每個距離段所用的時間。d[0]=0;for (i=0;i<a[n];i++){if (i<r)temp=1/(v-f*(r-i));elsetemp=1/(v-e*(i-r));d[i+1]=d[i]+temp;},2011-12-29,13,1264 Atomic Car Race,再給出每兩個檢查點（包括起點）之間的用

8、時。for (i=0;i<n;i++)for (j=i+1;j<=n;j++)c[i][j]=d[a[j]-a[i]];,2011-12-29,14,1264 Atomic Car Race,再用遞歸的方法進行動態(tài)規(guī)劃。dp[i][j]=min{c[i][j],dp[i][k]+dp[k][j]+b | i<k<j},2011-12-29,15,1264 Atomic Car Race,doubl

9、e cal(int s,int t) {if (visited[s][t])return dp[s][t];visited[s][t]=true;dp[s][t]=c[s][t];for (int i=s+1;i<t;i++) {double temp=cal(s,i)+cal(i,t)+b;if (temp<dp[s][t])dp[s][t]=temp;}return dp

10、[s][t];},2011-12-29,16,1828 Minimal,題目大意：給出兩個集合S1，S2，在S2中選出一些不重復的數(shù)與S1每個數(shù)匹配，使得匹配的數(shù)的差的絕對值盡量小。集合中數(shù)的個數(shù)不超過500。,2011-12-29,17,1828 Minimal,解題思路：首先證明，在S1中取兩個數(shù)a1,b1，在S2中取兩個數(shù)a2,b2，若a1<b1,a2<b2，則|a1-a2|+|b1-b2|<|a1-b

11、2|+|a2-b1|。即對于已排序的S1的數(shù)，只會按順序?qū)?yīng)已排序的S2的數(shù)。dp[i][j]表示S1中前i個數(shù)與S2中前j個數(shù)匹配時，第i個數(shù)或之前的匹配數(shù)值差的絕對值之和。,2011-12-29,18,1828 Minimal,sort(s1,s1+n);sort(s2,s2+m);dp[0][0]=abs(s1[0]-s2[0]);for (i=1;i<m;i++) dp[0][i]=min(dp[0][i-

12、1],abs(s1[0]-s2[i])); for (i=1;i<n;i++){ dp[i][i]=dp[i-1][i-1]+abs(s1[i]-s2[i]); for (j=i+1;j<m;j++) dp[i][j]=min(dp[i][j-1],dp[i-1][j-1]+abs(s1[i]-s2[j])); },2011-12-29,19,1527 Tiling a

13、Grid With Dominoes,題目大意：用1*2的長方形鋪滿4*N的長方形，有多少種方法。,2011-12-29,20,1527 Tiling a Grid With Dominoes,解題思路：和1121一樣，找出不同的缺口。用0表示缺口無方塊，1表示有。0:0000 1:0011 2:1100 3:1001 4:0110 5:1111狀態(tài)轉(zhuǎn)移：0->1, 0->2, 0->3, 0->5, 1

14、->2, 1->0, 2->1, 2->0, 3->0, 3->4, 4->3, 5->0, 0->0,2011-12-29,21,1527 Tiling a Grid With Dominoes,dp[0][0]=1;for (i=1;i<=n+1;i++) {dp[i][0]+=dp[i-1][0];dp[i][1]+=dp[i-1][0];dp[i][2]

15、+=dp[i-1][0];dp[i][3]+=dp[i-1][0];dp[i][5]+=dp[i-1][0];dp[i][2]+=dp[i-1][1];dp[i][0]+=dp[i-1][1];dp[i][1]+=dp[i-1][2];dp[i][0]+=dp[i-1][2];dp[i][0]+=dp[i-1][3];dp[i][4]+=dp[i-1][3];dp[i][3]+=dp[i-1][4];

16、dp[i][0]+=dp[i-1][5];},2011-12-29,22,1148 過河,題目大意：橋的起點為0，終點為L，其中地有M個石子。青蛙每次跳的范圍為[S,T]，問要跳過橋最小踩到石子次數(shù)。1 <= L <= 10^91 <= S <= T <= 101 <= M <= 100,2011-12-29,23,1148 過河,解題思路：L的值大太，直接按L的值進行動態(tài)規(guī)劃不

17、可行。分情況：若S和T相等，則踩到的石子數(shù)是固定的；若S和T不相等，因為S和T的最大值為10，所以當兩個石子相差太遠是沒有意義的，這里取的值為90，當石子距離相差90以上時，看作90，答案不變。壓縮后橋長度不超過10000，直接動態(tài)規(guī)劃即可。,2011-12-29,24,1148 過河,for(i=0;i90)delta[i]=90;}for(i=1;i<=m;i++)rock[i]=rock[i-1]+delta[

18、i-1];for(i=1;i<=m;i++)dp[rock[i]]=1;f[0]=1;work();,2011-12-29,25,1148 過河,void work() {L=rock[m]+90;for(i=s;i=0)if(f[j]&&dp[j]+dp[i]<max) {max=dp[j]+dp[i];f[i]=1;}dp[i]=max;

19、}},2011-12-29,26,1176 Two Ends,題目大意：兩個人輪流從一列數(shù)中取數(shù)，只能從兩端取。第一個人可以用任意策略，第二個人貪心每次取最大的數(shù)。一個人的分數(shù)等于他取的數(shù)的總和。問分數(shù)差值最大為多少。n<=1000,2011-12-29,27,1176 Two Ends,解題思路：每次到第一個人取數(shù)時，求出分別取左端和右端的值的最大分數(shù)，取其中的最大值。狀態(tài)dp[l][r]表示余下原序列的 [l..

20、r]這部分未取可得到的最優(yōu)值。,2011-12-29,28,1176 Two Ends,int cal(int l,int r) { if (l>r) return 0; if (visited[l][r]) return dp[l][r]; visited[l][r]=true; if ((r-l+1)%2==1) { if (a[l]>=a[

21、r]) return dp[l][r]=cal(l+1,r)-a[l]; else return dp[l][r]=cal(l,r-1)-a[r]; } else return dp[l][r]=max(cal(l+1,r)+a[l],cal(l,r-1)+a[r]);},2011-12-29,29,1163 Tour,題目大意：有一個人

22、要從起點開始經(jīng)過所有目的地再回到起點。他只能從起點（最左端的點），向右一直到達最右端的點，再返回起點，在這一次往返要經(jīng)過所有的點。求最短路程。,2011-12-29,30,1163 Tour,解題思路：一次往返可以看作從最左端點到最右端點的兩條獨立路徑。對所有點按從左到右排序后，用dp[i][j]表示兩條路徑現(xiàn)在分別在i和j點。假設(shè)i>j，則現(xiàn)在輪到枚舉第i+1個點，則可以從i到達第i+1個點，也可以j到達第i+1個點。,20

23、11-12-29,31,1163 Tour,for (i=0;ij) { if (i-1>j) dp[i][j]=dp[i-1][j]+d[i-1][i]; else { for (k=0;ktemp) dp[i][j]=temp; }

24、 } } else if (j>i) { /* similar to (i>j) */ } },2011-12-29,32,1345 能量項鏈,題目大意：給出一串項鏈，每次可以選相鄰兩個珠子進行聚合，釋放出一定的能量，并產(chǎn)生一個新珠子。項鏈是頭尾相接的。求釋放的能量的總和的最大值。項鏈長度不超過100。,2011-12-29,33,1345

25、 能量項鏈,解題思路：每次聚合，都會使數(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ū)間的長度從小到大。,2011-12-29,34,1345 能量項鏈,for

26、 (step=1;step=n*2) break; for (k=i;k<j;k++) temp=ans[i][k]+ans[k+1][j]+a[i]*a[k+1]*a[j+1]; if (ans[i][j]<temp) ans[i][j]=temp; },2011-12-29,35,1687 Permutation,題目

27、大意：n個數(shù)的排列，可以在中間插入小于號和大于號，如1 3 5 4 2 變成 14>2?，F(xiàn)在問n個數(shù)其中有k個小于號的排列有多少個。n,k<=100,2011-12-29,36,1687 Permutation,解題思路：用dp[i][j]表示i個數(shù)的排列有j個小于號，現(xiàn)在要擴展到i+1個數(shù)的排列，即插入一個數(shù)要大于當前所有數(shù)。當這個數(shù)插入位置為序列頭或小于號中間時，排列比原來多出一個大于號。當這個數(shù)插入位置為序列尾

28、或大于號中間時，排列比原來多出一個小于號。,2011-12-29,37,1687 Permutation,for (i=1;i<100;i++)for (j=0;j<i;j++){dp[i+1][j]+=dp[i][j]*(j+1);dp[i+1][j]%=2007;dp[i+1][j+1]+=dp[i][j]*(i-j);dp[i+1][j+1]%=2007;},2011-12-29,3