NOIP復(fù)習(xí)(動(dòng)態(tài)規(guī)劃)

1、 NOIP復(fù)習(xí)第三章：動(dòng)態(tài)規(guī)劃分類(lèi)： NOIP Wikioi ACM-ICPC/藍(lán)橋杯/其他大學(xué)競(jìng)賽 動(dòng)態(tài)規(guī)劃2014-09-01 08:15 458人閱讀 評(píng)論(0) 收藏 舉報(bào)目錄(?)+一、背包問(wèn)題最基礎(chǔ)的一類(lèi)動(dòng)規(guī)問(wèn)題，相似之處在于給n個(gè)物品或無(wú)窮多物品或不同種類(lèi)的物品，每種物品只有一個(gè)或若干個(gè)，給一個(gè)背包裝入這些物品，要求在不超出背包容量的范圍內(nèi)，使得獲得的價(jià)值或占用體積盡可能大，這一類(lèi)題的動(dòng)規(guī)方程fi一般表示剩余容量為i時(shí)取得的最大價(jià)值或最大占用體積，或者有多維狀態(tài)，分別表示不同種物品的剩余量1

2、、Wikioi 1014 裝箱問(wèn)題題目描述 Description有一個(gè)箱子容量為V（正整數(shù)，0V20000），同時(shí)有n個(gè)物品（0n30），每個(gè)物品有一個(gè)體積（正整數(shù)）。要求n個(gè)物品中，任取若干個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。輸入描述 Input Description一個(gè)整數(shù)v，表示箱子容量一個(gè)整數(shù)n，表示有n個(gè)物品接下來(lái)n個(gè)整數(shù)，分別表示這n 個(gè)物品的各自體積輸出描述 Output Description一個(gè)整數(shù)，表示箱子剩余空間。樣例輸入 Sample Input2468312797樣例輸出 Sample Output0一道

3、經(jīng)典的背包動(dòng)規(guī)，用數(shù)組f進(jìn)行動(dòng)規(guī)，fv=剩余容量為v時(shí)可以利用的最大體積，那么可以在每次輸入一個(gè)物品體積cost時(shí)遍歷剩余容量狀態(tài)，當(dāng)前狀態(tài)的剩余容量為v時(shí)，可以選擇裝入物品(裝入物品則當(dāng)前狀態(tài)可以利用的體積為fv-cost+cost)或不裝入物品,推出動(dòng)規(guī)方程:fv=maxfv-cost+costcpp view plaincopyprint?1. #include <stdio.h>  2. #include <string.h>  3.   4. #define M

4、AXN 30000  5.   6. int fMAXN; /fi=剩余體積為i時(shí)裝入物品的最大體積  7.   8. int max(int a,int b)  9.   10.     if(a>b) return a;  11.     return b;  

5、;12.   13.   14. int main()  15.   16.     int v,n,cost;  17.     scanf("%d%d",&v,&n);  18.     for(int i=1;i<=n;i+)   19.  

6、     20.         scanf("%d",&cost);  21.         for(int j=v;j>=cost;j-)  22.             fj=

7、max(fj,fj-cost+cost);  23.       24.     printf("%dn",v-fv);  25.     return 0;  26.    2、Wikioi 1068 烏龜棋題目描述 Description小明過(guò)生日的時(shí)候，爸爸送給他一副烏龜棋當(dāng)作禮物。 烏龜棋的棋盤(pán)是一行N個(gè)格子，每個(gè)格子上

8、一個(gè)分?jǐn)?shù)（非負(fù)整數(shù)）。棋盤(pán)第1格是唯一 的起點(diǎn)，第N格是終點(diǎn)，游戲要求玩家控制一個(gè)烏龜棋子從起點(diǎn)出發(fā)走到終點(diǎn)。 1 2 3 4 5 N 烏龜棋中M張爬行卡片，分成4種不同的類(lèi)型（M張卡片中不一定包含所有4種類(lèi)型 的卡片，見(jiàn)樣例），每種類(lèi)型的卡片上分別標(biāo)有1、2、3、4四個(gè)數(shù)字之一，表示使用這種卡 片后，烏龜棋子將向前爬行相應(yīng)的格子數(shù)。游戲中，玩家每次需要從所有的爬行卡片中選擇 一張之前沒(méi)有使用過(guò)的爬行卡片，控制烏龜棋子前進(jìn)相應(yīng)的格子數(shù)，每張卡片只能使用一次。 游戲中，烏龜棋子自動(dòng)獲得起點(diǎn)格子的分?jǐn)?shù)，并且在后續(xù)的爬行中每到達(dá)一個(gè)格子，就得到 該格子相應(yīng)的分?jǐn)?shù)。玩家最終游戲得分就是烏龜棋子從起點(diǎn)到

9、終點(diǎn)過(guò)程中到過(guò)的所有格子的 分?jǐn)?shù)總和。 很明顯，用不同的爬行卡片使用順序會(huì)使得最終游戲的得分不同，小明想要找到一種卡 片使用順序使得最終游戲得分最多。 現(xiàn)在，告訴你棋盤(pán)上每個(gè)格子的分?jǐn)?shù)和所有的爬行卡片，你能告訴小明，他最多能得到 多少分嗎？輸入描述 Input Description輸入的每行中兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。 第1行2個(gè)正整數(shù)N和M，分別表示棋盤(pán)格子數(shù)和爬行卡片數(shù)。 第2行N個(gè)非負(fù)整數(shù)，a1a2aN，其中ai表示棋盤(pán)第i個(gè)格子上的分?jǐn)?shù)。 第3行M個(gè)整數(shù)，b1b2bM，表示M張爬行卡片上的數(shù)字。 輸入數(shù)據(jù)保證到達(dá)終點(diǎn)時(shí)剛好用光M張爬行卡片，即N - 1=(1->M)

10、bi輸出描述 Output Description輸出一行一個(gè)整數(shù)樣例輸入 Sample Input13 84 96 10 64 55 13 94 53 5 24 89 8 301 1 1 1 1 2 4 1樣例輸出 Sample Output455數(shù)據(jù)范圍及提示 Data Size & Hint【數(shù)據(jù)范圍】對(duì)于30%的數(shù)據(jù)有1  

11、;N 30，1 M 12。對(duì)于50%的數(shù)據(jù)有1  N 120，1 M 50，且4 種爬行卡片，每種卡片的張數(shù)不會(huì)超過(guò)20。對(duì)于100%的數(shù)據(jù)有1  N 350，1 M 120，且4 種爬行卡片，每種卡片的張數(shù)不會(huì)超過(guò)40；0  ai  100，1  i  N；1  bi  4，1  i M。輸入數(shù)據(jù)

12、保證N1=Mi b1可以說(shuō)這是一道背包的變形題，不再是只有單一的狀態(tài)(剩余體積)，實(shí)際上因?yàn)榭ㄆ址N類(lèi)，導(dǎo)致?tīng)顟B(tài)變成了4個(gè)：4種爬行卡片分別剩余的張數(shù)，則可用數(shù)組f來(lái)進(jìn)行動(dòng)規(guī)，fijkh=1、2、3、4號(hào)卡片各用掉i,j,k,h張時(shí)，下棋獲得的最大分?jǐn)?shù)，則每次從小到大動(dòng)規(guī)，經(jīng)過(guò)狀態(tài)fijkh時(shí)，考慮用掉一張1或2或3或4號(hào)卡片，那么這次操作之前得到的分?jǐn)?shù)就是fi-1kjh或fik-1jh或fikj-1h或fikjh-1(注：上次操作得到的分?jǐn)?shù)并不包含上次操作后到達(dá)的格子分?jǐn)?shù))，然后再加上上次操作后到達(dá)的格子分?jǐn)?shù)，這次操作到達(dá)的格子分?jǐn)?shù)就等到下次操作時(shí)再算。最后輸出fcard1card

13、2card3card4+mapn,cardx=第x種卡片的張數(shù)，mapn=終點(diǎn)的分?jǐn)?shù)。當(dāng)然也可以先算上起點(diǎn)的格子分?jǐn)?shù)，每次決策時(shí)不加上次操作到達(dá)的格子分?jǐn)?shù)，而是加上本次操作到達(dá)的格子分?jǐn)?shù)，或許更便于理解cpp view plaincopyprint?1. #include <stdio.h>  2. #include <string.h>  3.   4. #define MAXM 40  5. #define MAXN 

14、400  6.   7. int fMAXMMAXMMAXMMAXM; /fijkh=1 2 3 4四種卡片各用了i,j,k,h張時(shí)的最高分?jǐn)?shù)  8. int mapMAXN; /棋盤(pán)上的分?jǐn)?shù)  9.   10. int max(int a,int b)  11.   12.     if(a>b) r

15、eturn a;  13.     return b;  14.   15.   16. int main()  17.   18.     int n,m;  19.     int card5=0;  20.     scan

16、f("%d%d",&n,&m);  21.     for(int i=1;i<=n;i+)  22.         scanf("%d",&mapi);  23.     for(int i=0;i<m;i+)  24.    &

17、#160;  25.         int kind;  26.         scanf("%d",&kind);  27.         cardkind+;  28.      &

18、#160;29.     for(int i=0;i<=card1;i+)  30.         for(int j=0;j<=card2;j+)  31.             for(int k=0;k<=card3;k+)  32.

19、60;               for(int h=0;h<=card4;h+)  33.                   34.         

20、;            int dis=i*1+j*2+k*3+h*4; /dis=當(dāng)前用了i,j,k,h張牌后烏龜棋移動(dòng)的距離  35.                     if(i>=1) fijkh=max(fi

21、jkh,fi-1jkh+map1+(i-1)*1+j*2+k*3+h*4);  36.                     if(j>=1) fijkh=max(fijkh,fij-1kh+map1+i*1+(j-1)*2+k*3+h*4);  37.        &

22、#160;            if(k>=1) fijkh=max(fijkh,fijk-1h+map1+i*1+j*2+(k-1)*3+h*4);  38.                     if(h>=1) fij

23、kh=max(fijkh,fijkh-1+map1+i*1+j*2+k*3+(h-1)*4);  39.                   40.     printf("%dn",fcard1card2card3card4+mapn);  41.     return

24、0;0;  42.   3、POJ 1276 Cash Machine(多重背包經(jīng)典題)/problem?id=1276題目大意：要用n種錢(qián)幣湊面額cash，要取湊到的面額必須小于等于Cash，給定每種錢(qián)幣的面值和張數(shù)，求最多能湊到的面額。經(jīng)典的多重背包題，可以將每種錢(qián)幣當(dāng)成物品，錢(qián)幣的體積和價(jià)值均為它的面值。cpp view plaincopyprint?1. #include <iostream>  2. #include <stdio.h> 

25、; 3. #include <string.h>  4. #include <stdlib.h>  5.   6. #define MAXN 11  7. #define MAXV 100010  8.   9. using namespace std;  10.   11. struct Thing &

26、#160;12.   13.     int n,v,w; /n件，價(jià)值為v，體積為w，在這個(gè)題中v=w  14. thingsMAXN;/保存每種紙幣個(gè)數(shù)  15.   16. bool canGetMAXV; /canGeti=true表示面額i可以被取到  17.   18. int main()  19.   20.   

27、;  int cash,n;  21.     while(scanf("%d%d",&cash,&n)!=EOF)  22.       23.         int i,j,ans=0; /要取的面額為cash,n種錢(qián)幣  24.    

28、     for(int i=1;i<=n;i+)  25.           26.             scanf("%d%d",&thingsi.n,&thingsi.v);  27.    &#

29、160;        thingsi.w=thingsi.v;  28.           29.         if(!cash|!n)  30.           31.  &#

30、160;          printf("0n");  32.             continue;  33.           34.       

31、  memset(canGet,false,sizeof(canGet);  35.         canGet0=true; /面額為0當(dāng)然可以取到  36.         for(i=1,ans=0;i<=n;i+) /正在取第i種錢(qián)幣  37.       

32、60;     for(j=ans;j>=0;j-) /取到的面額為j  38.                 if(canGetj) /面額j可以取到  39.              &

33、#160;      for(int k=1;k<=thingsi.n;k+) /第i種物品取n個(gè)  40.                       41.          &#

34、160;              int temp=j+k*thingsi.w;  42.                         if(temp>cash) /取

35、的面額超過(guò)了cash,太多了  43.                             break;  44.              &#

36、160;          canGettemp=true;  45.                         if(temp>ans) ans=temp;  46.   &#

37、160;                   47.         cout<<ans<<endl;  48.       49.     return 0; &#

38、160;50.   4、POJ 1742 Coins（帶優(yōu)化的多重背包）/problem?id=1742樓教主的經(jīng)典題，題目大意是要用多種錢(qián)幣湊出一個(gè)面額，這個(gè)面額小于等于v，給出每種錢(qián)幣的面值和個(gè)數(shù)，求最終能湊出多少種面額cpp view plaincopyprint?1. #include <iostream>  2. #include <stdio.h>  3. #include <string.h>  4.

39、 #include <stdlib.h>  5. #include <algorithm>  6.   7. #define MAXN 110  8. #define MAXV 100100  9.   10. using namespace std;  11.   12. struct Thing  1

40、3.   14.     int n,v,w; /個(gè)數(shù)為n，價(jià)值為v，體積為w  15. coinsMAXN;  16.   17. bool canGetMAXV; /canGeti=true表示面額i可以被取到  18. int n,v;  19.   20. void ZeroOnePack(int cost) /01背包 

41、; 21.   22.     for(int i=v;i>=cost;i-)  23.         canGeti|=canGeti-cost;  24.   25.   26. void CompletePack(int cost) /完全背包  27.   28. 

42、0;   for(int i=cost;i<=v;i+)  29.         canGeti|=canGeti-cost;  30.   31.   32. void MultiplePack(int cost,int amount) /多重背包  33.   34.    &

43、#160;if(cost*amount>=v)  35.       36.         CompletePack(cost); /轉(zhuǎn)換為完全背包問(wèn)題  37.         return;  38.       39.  &#

44、160;  int k=1; /拿k件同樣的物品  40.     while(k<amount)  41.       42.         ZeroOnePack(k*cost);  43.         amount-=k;

45、  44.         k<<=1; /k<-k*2  45.       46.     ZeroOnePack(amount*cost);  47.   48.   49. int main()  50.   51.  &#

46、160;  while(scanf("%d%d",&n,&v)  52.       53.         int ans=0;  54.         if(!n|!v) break;  55.    

47、60;    for(int i=1;i<=n;i+) scanf("%d",&coinsi.w);  56.         for(int i=1;i<=n;i+) scanf("%d",&coinsi.n);  57.         memse

48、t(canGet,false,sizeof(canGet);  58.         canGet0=true;  59.         for(int i=1;i<=n;i+) /當(dāng)前正在嘗試湊的硬幣為第i個(gè)硬幣  60.           &#

49、160; if(coinsi.n) /這個(gè)硬幣有剩余  61.                 MultiplePack(coinsi.w,coinsi.n);  62.         for(int i=1;i<=v;i+) /面額為i  63. &

50、#160;           if(canGeti) /面額為i的可以取到  64.                 ans+;  65.         cout<<ans<&l

51、t;endl;  66.       67.     return 0;  68.   二、區(qū)間型動(dòng)態(tài)規(guī)劃這一類(lèi)題目的相似之處在于動(dòng)規(guī)方程fi表示以i結(jié)尾的價(jià)值/數(shù)量等等的大小，在決策時(shí)尋找i之前的位置j，使得fi取得最值3、Wikioi 1044 攔截導(dǎo)彈題目描述 Description    某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈

52、能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。  輸入描述 Input Description輸入導(dǎo)彈依次飛來(lái)的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)）  輸出描述 Output Description輸出這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。樣例輸入 Sample Input389 207 155 300 299 170 158 65 樣例輸

53、出 Sample Output62數(shù)據(jù)范圍及提示 Data Size & Hint導(dǎo)彈的高度<=30000，導(dǎo)彈個(gè)數(shù)<=20可以把導(dǎo)彈的高度化為一個(gè)數(shù)字序列，由題意可知，一個(gè)導(dǎo)彈攔截的目標(biāo)必為原序列的不上升子序列，要想讓攔截目標(biāo)個(gè)數(shù)盡量多，就要求這個(gè)不上升子序列是最長(zhǎng)的，換句話說(shuō)，第一問(wèn)就是求不上升子序列，第二問(wèn)略微麻煩點(diǎn)，要讓所有目標(biāo)都被打而且導(dǎo)彈盡量少，那么需要每個(gè)導(dǎo)彈不光打一個(gè)目標(biāo)，而且要把以這個(gè)目標(biāo)為頭的不上升子序列都打到，如圖，綠色的線就是不上升子序列，紅色的線是嚴(yán)格上升子序列，很明顯，第二問(wèn)要求最長(zhǎng)嚴(yán)格上升子序列，這個(gè)子序列中的所有元素都需要

54、一發(fā)導(dǎo)彈，而它們連接的不上升子序列都能被這些導(dǎo)彈打到，第二問(wèn)的答案就是最長(zhǎng)嚴(yán)格上升子序列。cpp view plaincopyprint?1. #include <stdio.h>  2. #include <string.h>  3. #include <stdlib.h>  4.   5. #define MAXN 1000  6.   7. int upMAXN,d

55、nMAXN;  8. int highMAXN,cnt=0;  9. int maxDN=-1,maxUP=-1;  10.   11. int max(int a,int b)  12.   13.     if(a>b) return a;  14.     return b; 

56、 15.   16.   17. int main()  18.   19.     while(scanf("%d",&high+cnt)!=EOF);  20.     for(int i=1;i<=cnt;i+)  21.         for(i

57、nt j=1;j<i;j+)  22.           23.             if(highi>highj)  24.               25. 

58、0;               upi=max(upi,upj+1);  26.               27.             if(highi<=

59、highj)  28.               29.                 dni=max(dni,dnj+1);  30.           

60、;    31.           32.     for(int i=1;i<=cnt;i+)  33.       34.         maxDN=max(maxDN,dni);  35.   

61、      maxUP=max(maxUP,upi);  36.       37.     printf("%dn%dn",maxDN,maxUP+1);  38.     return 0;  39.   4、Wikioi 3027 線段覆蓋2題目描述 Description

62、數(shù)軸上有n條線段，線段的兩端都是整數(shù)坐標(biāo)，坐標(biāo)范圍在01000000，每條線段有一個(gè)價(jià)值，請(qǐng)從n條線段中挑出若干條線段，使得這些線段兩兩不覆蓋（端點(diǎn)可以重合）且線段價(jià)值之和最大。n<=1000輸入描述 Input Description第一行一個(gè)整數(shù)n，表示有多少條線段。接下來(lái)n行每行三個(gè)整數(shù), ai bi ci，分別代表第i條線段的左端點(diǎn)ai，右端點(diǎn)bi（保證左端點(diǎn)<右端點(diǎn)）和價(jià)值ci。輸出描述 Output Description輸出能夠獲得的最大價(jià)值樣例輸入 Sample Input31 2 12 3 21 3 4樣例輸出 Sample

63、 Output4數(shù)據(jù)范圍及提示 Data Size & Hint數(shù)據(jù)范圍對(duì)于40%的數(shù)據(jù)，n10；對(duì)于100%的數(shù)據(jù)，n1000；0<=ai,bi<=10000000<=ci<=1000000首先需要把所有線段根據(jù)右端點(diǎn)升序排序，這樣的話，找與第i條線段不重合的線段j，就只需要往前找一個(gè)線段j，使得j的右端點(diǎn)小于等于i的左端點(diǎn)坐標(biāo)，然后開(kāi)一個(gè)數(shù)組f進(jìn)行動(dòng)規(guī)，數(shù)組fi=前i條線段，第i條線段必選，獲得的最大價(jià)值，那么對(duì)于每一條線段i，在這條線段之前找一條不和它重合的線段j，使得fj+valuei取得最大值，DP方程為:fi=maxfj+valuei,j&

64、lt;i且線段i不與j重合  cpp view plaincopyprint?1. #include <stdio.h>  2. #include <string.h>  3. #include <algorithm>  4.   5. #define MAXN 1100  6.   7. using namespace std; 

65、 8.   9. struct Line  10.   11.     int L,R,w; /左端點(diǎn)，右端點(diǎn)，線段權(quán)值  12. lineMAXN;  13.   14. bool cmp(Line a,Line b)  15.   16.     return a.R<

66、b.R;  17.   18.   19. int fMAXN; /fi=前i條線段，第i條線段必選，獲得的最大價(jià)值  20.   21. int main()  22.   23.     int n,ans=-1;  24.     scanf("%d",&n);  

67、25.     for(int i=1;i<=n;i+)  26.         scanf("%d%d%d",&linei.L,&linei.R,&linei.w);  27.     sort(line+1,line+n+1,cmp);  28.     for(int&#

68、160;i=1;i<=n;i+) fi=linei.w;  29.     for(int i=2;i<=n;i+)  30.       31.         for(int j=1;j<i;j+) /找到第i條線段之前的一條線段j,兩條線段互不重合，這樣就能把i插到j(luò)的后面  32.  

69、;           if(linei.L>=linej.R)  33.               34.                 fi=max(fi,

70、linei.w+fj);  35.               36.       37.     for(int i=1;i<=n;i+)  38.         ans=max(ans,fi); /找到了一個(gè)

71、結(jié)尾i，使得fi最大  39.     printf("%dn",ans);  40.     return 0;  41.   三、區(qū)間型動(dòng)態(tài)規(guī)劃這一類(lèi)題的解法通常是開(kāi)動(dòng)規(guī)數(shù)組f(一般是兩維)，fij表示區(qū)間i,j獲得的最值，決策時(shí)尋找一個(gè)屬于該區(qū)間的中點(diǎn)k，使fik+fk+1j取得最值，并用來(lái)更新fij5、Wikioi 石子合并題目描述 Description有n堆石子排成一列，每堆石子有一個(gè)

72、重量wi, 每次合并可以合并相鄰的兩堆石子，一次合并的代價(jià)為兩堆石子的重量和wi+wi+1。問(wèn)安排怎樣的合并順序，能夠使得總合并代價(jià)達(dá)到最小。輸入描述 Input Description第一行一個(gè)整數(shù)n（n<=100）第二行n個(gè)整數(shù)w1,w2.wn  (wi <= 100)輸出描述 Output Description一個(gè)整數(shù)表示最小合并代價(jià)樣例輸入 Sample Input44 1 1 4樣例輸出 Sample Output18數(shù)據(jù)范圍及提示 Data Size & Hint這個(gè)題很明顯是一個(gè)區(qū)間型動(dòng)規(guī)，用fij

73、表示將區(qū)間i,j合并時(shí)的最小代價(jià)，則每次決策時(shí)尋找一個(gè)中點(diǎn)k，使得fik+fk+1j最小，并更新fij另外這個(gè)題需要注意一下，i是從大到小枚舉的，我個(gè)人理解是：i從大到小枚舉，最開(kāi)始動(dòng)規(guī)決策時(shí)需要的已求出的f就很少，否則剛開(kāi)始決策時(shí)很多需要的f沒(méi)有求出來(lái)，答案就會(huì)錯(cuò)誤 cpp view plaincopyprint?1. #include <stdio.h>  2. #include <string.h>  3. #include <stdlib.h> 

74、60;4.   5. #define MAXN 1000  6. #define INF 10000000  7.   8. int fMAXNMAXN; /fij=合并區(qū)間i,j所獲得的最大價(jià)值  9. int sumMAXN;  10.   11. int min(int a,int b)  12.   13. &

75、#160;   if(a<b) return a;  14.     return b;  15.   16.   17. int main()  18.   19.     int n;  20.     scanf("%d",&a

76、mp;n);  21.     for(int i=1;i<=n;i+)  22.       23.         int w;  24.         scanf("%d",&w);  25. &#

77、160;       sumi=sumi-1+w;  26.       27.     for(int i=n-1;i>=1;i-)  28.         for(int j=i+1;j<=n;j+)  29.    &#

78、160;      30.             int minAns=INF;  31.             for(int k=i;k<j;k+)  32.      

79、60;        33.                 minAns=min(minAns,fik+fk+1j+sumj-sumi-1);  34.               35. 

80、0;           fij=minAns;  36.           37.     printf("%dn",f1n);  38.     return 0;  39.   6、Wikio

81、i 1154 能量項(xiàng)鏈題目描述 Description在Mars星球上，每個(gè)Mars人都隨身佩帶著一串能量項(xiàng)鏈。在項(xiàng)鏈上有N顆能量珠。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。并且，對(duì)于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。因?yàn)橹挥羞@樣，通過(guò)吸盤(pán)（吸盤(pán)是Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時(shí)釋放出可以被吸盤(pán)吸收的能量。如果前一顆能量珠的頭標(biāo)記為m，尾標(biāo)記為r，后一顆能量珠的頭標(biāo)記為r，尾標(biāo)記為n，則聚合后釋放的能量為m*r*n（Mars單位），新產(chǎn)生的珠子的頭標(biāo)記為m，尾標(biāo)記為n。需要時(shí)，Mars人就用吸盤(pán)

82、夾住相鄰的兩顆珠子，通過(guò)聚合得到能量，直到項(xiàng)鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請(qǐng)你設(shè)計(jì)一個(gè)聚合順序，使一串項(xiàng)鏈釋放出的總能量最大。例如：設(shè)N=4，4顆珠子的頭標(biāo)記與尾標(biāo)記依次為(2，3) (3，5) (5，10) (10，2)。我們用記號(hào)表示兩顆珠子的聚合操作，(jk)表示第j，k兩顆珠子聚合后所釋放的能量。則第4、1兩顆珠子聚合后釋放的能量為：(41)=10*2*3=60。這一串項(xiàng)鏈可以得到最優(yōu)值的一個(gè)聚合順序所釋放的總能量為(41)2)3）=10*2*3+10*3*5+10*5*10=710。輸入描述 Input Description第一行是一個(gè)

83、正整數(shù)N（4N100），表示項(xiàng)鏈上珠子的個(gè)數(shù)。第二行是N個(gè)用空格隔開(kāi)的正整數(shù)，所有的數(shù)均不超過(guò)1000。第i個(gè)數(shù)為第i顆珠子的頭標(biāo)記（1iN），當(dāng)i<N< span>時(shí)，第i顆珠子的尾標(biāo)記應(yīng)該等于第i+1顆珠子的頭標(biāo)記。第N顆珠子的尾標(biāo)記應(yīng)該等于第1顆珠子的頭標(biāo)記。至于珠子的順序，你可以這樣確定：將項(xiàng)鏈放到桌面上，不要出現(xiàn)交叉，隨意指定第一顆珠子，然后按順時(shí)針?lè)较虼_定其他珠子的順序。輸出描述 Output Description只有一行，是一個(gè)正整數(shù)E（E2.1*109），為一個(gè)最優(yōu)聚合順序所釋放的總能量。樣例輸入 Sample Input42 3 5 1

84、0樣例輸出 Sample Output710這個(gè)題同樣是區(qū)間型動(dòng)態(tài)規(guī)劃，和上一題很相似，最大的不同在于這個(gè)題的區(qū)間是一個(gè)環(huán)形的(沒(méi)有起點(diǎn)和終點(diǎn))，通常處理這種環(huán)形區(qū)間的問(wèn)題，可以把有n個(gè)元素的環(huán)看作2*n長(zhǎng)度的區(qū)間，n+1,2*n從1,n復(fù)制而來(lái)，這樣就不存在區(qū)間終點(diǎn)該怎么和起點(diǎn)連接的問(wèn)題，然后動(dòng)規(guī)時(shí)需要先枚舉一個(gè)合并區(qū)間的起點(diǎn)i，那么合并區(qū)間就是i,i+n-1，然后環(huán)形區(qū)間就轉(zhuǎn)化成了一個(gè)直線區(qū)間，動(dòng)規(guī)過(guò)程類(lèi)似于上一題，時(shí)間復(fù)雜度O(n4)cpp view plaincopyprint?1. #include <stdio.h>  

85、2. #include <string.h>  3. #include <stdlib.h>  4.   5. #define MAXN 1000  6.   7. struct node  8.   9.     int head,tail;  10. ballMAXN;  11.  

86、; 12. int fMAXNMAXN; /fij=將i,j合并后獲得的最大能量  13.   14. int max(int a,int b)  15.   16.     if(a>b) return a;  17.     return b;  18.   19.  

87、 20. int getEnergy(int m,int r,int n)  21.   22.     return ballm.head*ballr.tail*balln.tail;  23.   24.   25. int main()  26.   27.     int n; &

88、#160;28.     scanf("%d",&n);  29.     for(int i=1;i<=n;i+)  30.       31.         scanf("%d",&balli.head);  32.   

89、      balli-1.tail=balli.head;  33.       34.     balln.tail=ball1.head;  35.     for(int i=1;i<=n;i+)  36.         balli+

90、n=balli;  37.     for(int i=1;i<=n;i+) /start from position i,i,i+n-1  38.         for(int j=i+n-2;j>=i;j-)  39.           4

91、0.             for(int k=j+1;k<=i+n-1;k+)  41.               42.               

92、60; int maxAns=-1;  43.                 for(int p=j;p<k;p+)  44.                    

93、60;maxAns=max(maxAns,fjp+fp+1k+getEnergy(j,p,k);  45.                 fjk=maxAns;  46.               47.     &

94、#160;     48.     int maxAns=-1;  49.     for(int i=1;i<=n;i+)  50.         maxAns=max(maxAns,fii+n-1);  51.     printf("%dn&qu

95、ot;,maxAns);  52.     return 0;  53.   四、棋盤(pán)型動(dòng)態(tài)規(guī)劃個(gè)人認(rèn)為這種動(dòng)規(guī)是最簡(jiǎn)單的，因?yàn)樗浅Ｐ蜗?，很好推?dǎo)出動(dòng)規(guī)方程，這一類(lèi)動(dòng)規(guī)大多開(kāi)二維動(dòng)規(guī)數(shù)組，代表棋盤(pán)里每個(gè)坐標(biāo)的狀態(tài)7、Wikioi 1010 過(guò)河卒 題目描述 Description如圖，A 點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo) B 點(diǎn)。卒行走規(guī)則：可以向下、或者向右。同時(shí)在棋盤(pán)上的任一點(diǎn)有一個(gè)對(duì)方的馬（如上圖的C點(diǎn)），該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)。例

96、如上圖 C 點(diǎn)上的馬可以控制 9 個(gè)點(diǎn)（圖中的P1，P2 P8 和 C）。卒不能通過(guò)對(duì)方馬的控制點(diǎn)。棋盤(pán)用坐標(biāo)表示，A 點(diǎn)（0，0）、B 點(diǎn)（n,m）(n,m 為不超過(guò) 20 的整數(shù)，并由鍵盤(pán)輸入)，同樣馬的位置坐標(biāo)是需要給出的（約定: C不等于A，同時(shí)C不等于B）?，F(xiàn)在要求你計(jì)算出卒從 A 點(diǎn)能夠到達(dá) B 點(diǎn)的路徑的條數(shù)。1<=n,m<=15輸入描述 Input Description鍵盤(pán)輸入B點(diǎn)的坐標(biāo)（n,m）以及對(duì)方馬的坐標(biāo)（X,Y）不用判錯(cuò)輸出描述 Output Description屏幕輸出一個(gè)整數(shù)（路徑的條數(shù)）。樣例輸入 Sample In

97、put6 6 3 2樣例輸出 Sample Output17數(shù)據(jù)范圍及提示 Data Size & Hint如描述這個(gè)題比較好做，只要在棋盤(pán)中標(biāo)明所有馬的控制點(diǎn)，動(dòng)規(guī)時(shí)避開(kāi)它們即可，fij表示經(jīng)過(guò)(i,j)的路徑條數(shù)，這個(gè)路徑條數(shù)實(shí)際上就等于其左邊的點(diǎn)和上方的點(diǎn)的路徑條數(shù)之和，因?yàn)槟莾蓚€(gè)點(diǎn)的路可以走到這個(gè)點(diǎn)，DP方程fij=fi-1j+fij-1,邊界條件f00=1(左上角的點(diǎn)只可能有一條路經(jīng)過(guò))  cpp view plaincopyprint?1. #include <stdio.h>  2

98、. #include <string.h>  3. #include <stdlib.h>  4.   5. #define MAXN 100  6.   7. int mapMAXNMAXN;  8. int fMAXNMAXN;  9. int n,m;  10.   11. bool inMap(int

99、60;x,int y)  12.   13.     if(x<0|x>n|y<0|y>m) return false;  14.     return true;  15.   16.   17. int main()  18.   19.    

100、60;int x,y;  20.     scanf("%d%d%d%d",&n,&m,&x,&y);  21.     if(inMap(x,y) mapxy=1;  22.     if(inMap(x+2,y+1) mapx+2y+1=1;  23.     if(inM

101、ap(x+2,y-1) mapx+2y-1=1;  24.     if(inMap(x-2,y+1) mapx-2y+1=1;  25.     if(inMap(x-2,y-1) mapx-2y-1=1;  26.     if(inMap(x+1,y+2) mapx+1y+2=1;  27.     if(inM

102、ap(x+1,y-2) mapx+1y-2=1;  28.     if(inMap(x-1,y+2) mapx-1y+2=1;  29.     if(inMap(x-1,y-2) mapx-1y-2=1;  30.     f00=1;  31.     for(int i=0;i<=n;i+) &

103、#160;32.         for(int j=0;j<=m;j+)  33.             if(!mapij)  34.               35.   &

104、#160;             if(inMap(i-1,j) fij+=fi-1j;  36.                 if(inMap(i,j-1) fij+=fij-1;  37.         &