noip2006解題報告

1、能量項鏈 本題是一道很經(jīng)典的dp題目，其實質就是“石子合并問題”的變形，有談不上什么變形，倒不如說復制更好一點。我想很多的牛人在這個題目失分的原因多為沒弄懂題目的意思就下手做了，把題目看簡單了。 簡單的說：給你一項鏈，項鏈上有n顆珠子。相鄰的兩顆珠子可以合并(兩個合并成一個)。合并的同時會放出一定的能量。不同的珠子的合并所釋放的能量是不同的。問：按照怎樣的次序合并才能使釋放的能量最多？我們用top表示第i顆珠子的頭標記，用wei表示第i顆珠子的尾標記，合并兩顆相鄰珠子所釋放的能量是：Q=top*wei*weii+1或top*topi+1*weii+1;（一個樣的）合并不一定按順序的，本題所提供

2、的樣例也是導致出錯的一大原因。n個珠子進行一次合并的后，就歸結到了n-1個珠子的合并的問題。所以我們想到了動態(tài)規(guī)劃。既然是dp題目，必然要滿足dp的兩大條件：、1.最優(yōu)子結構性質；設Qi,j表示第i顆珠子到第j顆珠子合并所產(chǎn)生的能量。顯然Q1,n表示的是合并產(chǎn)生的總的能量。給定一種標號方法，maxQ1,n就是所要求的。設最后一次合并在k處進行，則有Q1,nQ1,kQk+1,ntop1*weik*wein。要Q1,n最大，必然要Q1,k，Qk+1,n最大。證明：假設Q1,k不是最大，則必然存在一Q1,kQ1,k。 那么就有Q1,nQ1,kQk+1,ntop1*weik*weinQ1,k。這與Q1

3、,n的最優(yōu)性矛盾。最優(yōu)子結構性質得證。 2.無后效性； 無后效性是顯然的，進行某次合并，合并前與合并后狀態(tài)是相對獨立，不相關聯(lián)，互不影響的。算法已經(jīng)定了下來了，關鍵是怎么實現(xiàn)了。項鏈是一個環(huán)，而我們處理是對一個串進行的。所以我們要把項鏈從某處割斷展開，不同處的割斷對應著不同的展開方法，也就是對應著不同的標號方法。產(chǎn)生的maxQ1,n也就不同的。所以我們要對這些maxQ1,n進行打擂，取其最大的一個，即為解了。 dp的轉移方程是： Best=maxQ1,n 1=i=n (i表示從第i顆珠子處展開，順次標號）； Qi,j=maxQi,k+Qk+1,j+top*weik*weij1=i=kj=n ;

4、 其中Qi,i=01=i=n; dp的時間復雜度為O(n3)，n種的展開方法對應需要n次的dp，所以時間復雜度為O(n4)?？臻g為O(n2)。 顯然O(n4)過這個題目是有點欠缺的，對的大的數(shù)據(jù)貌似很容易超時的。如果仔細想想，我們還是做了很不重復的工作的，不同的展開方式中必然存在著很多的大量的重復運算。于是還有很大的優(yōu)化空間，既然展開做了很多的重復的工作，那么就合并起來吧?；氐狡瘘c，開始的時候為什么我們要對項鏈做n次的展開呢，基于我們在運算的時候不能夠實現(xiàn)第一顆珠子與第n顆珠子的相鄰性。為了一次dp就實現(xiàn)所以的的珠子的相鄰性，我們做如下處理：a1,a2,a3.an,a1,a2.an-1 （原來

5、的） （延伸的）也就是：a1,a2,a3.an,an+1,an+2.am顯然m=2n-1;我們對這一串珠子dp一次即可得解；dp方程為：Best=maxQi,i+n-11=i=n Qi,j=maxQi,k+Qk+1,j+top*weik*weij1=i=kj=min(i+n-1,m) 其中Qi,i=01=im then break; for k:=i to j-1 do if fi,jfi,k+fk+1,j+top*weik*weij then fi,j:=fi,k+fk+1,j+top*weik*weij end; end;procedure print; var i:integer; be

6、st:longint; begin best:=0; for i:=1 to n do if bestb then max:=a else max:=b;end;begin while not eof do begin readln(n); for i:=1 to n do begin read(ppi); ppi+n:=ppi; end;readln; w:=0; for x:=1 to n do begin for i:=1 to n+1 do pi:=ppi+x-1; for i:=1 to n do fi,1:=0; for i:=1 to n-1 do fi,2:=pi*pi+1*p

7、i+2; for k:=3 to n do begin for i:=1 to n-k+1 do begin fi,k:=0; for j:=1 to k-1 do begin fi,k:=max(fi,k,fi,j+fi+j,k-j+pi*pi+j*pi+k); end; end; end; if wf1,n then w:=f1,n; end; writeln(w); end; TODO -oUser -cConsole Main : Insert code here end.金明的預算方案如果看過普及組試卷就會發(fā)現(xiàn)，對應的第二個題目，也是一個樣的背景，提高組只是多了個“主件附件”的的關系

8、，如果去掉這一點，就全沒區(qū)別了。也就成了經(jīng)典的背包問題了。也就是多了這么一點，考試的時候就暈了。不知道怎么做了。后來才發(fā)現(xiàn)是個很簡單的dp題目。可惜我當時沒做出來。草率的審題，可能會得到這樣的算法：dp，對每一個物品做兩種決策，取與不取。如果取，滿足兩個條件：1.要么它是主件，要么它所屬的主件已經(jīng)在包里了。2.放進去后的重要度與價格的成績的總和要比沒放進時的大。這兩個條件缺一不可的。于是呼，得到如下的動規(guī)方程：fi,j:=fi-1,j; if(i為主件ori的附件在包中）and (fi,jfi,j-v+v*w) then fi,j:=fi,j-v+v*w;我們來分析一下復雜度，空間：dp的階段

9、為n2,對與每一個階段都要記錄該狀態(tài)下在包中的物品有哪些（因為要確定附件的主件是否在包中)，每個階段的記錄都要O(n)的空間，所以總的就是O(n3)。時間，一個dp，n2的外層循環(huán)，內部用布爾量加個主附件的對應數(shù)組，為O(1)，和起來就為O(n2)的復雜度。可以看的出，時間的需求為32000*60，不成問題?？臻g32000*60*60，大約要7.5M的空間，在64M的要求下是完全可以的過的。如果用上題目中的一個很隱秘的條件：“每件物品都是10元的整數(shù)倍”，就可以把速度在提高十倍。細細的看題目，還一個很重要的條件我們還沒用：“每個主件可以有個，個或個附件”。這貌似不起眼的一句話，卻給我們降低復雜

10、度提供了條件。想一想，為什么題目要對附件的個數(shù)做限制呢，明顯是在降低難度。對于一套物品（包含主件，所以的附件），我們稱為一個屬類，對一個屬類的物品的購買方法，有以下種：.一個都不買.主件.主件附件.主件附件.主件附件附件這五種購買方法也是唯一的五種方法，也就是說對一屬類的物品，我們只有上述的種購買方法。于是我們很自然的就會想到把物品按物品的屬類捆在一起考慮。這樣我們把物品的屬類作為dp的狀態(tài)。可以得到如下的dp方程：fi,j=maxfi-1,j; fi-1,j-vi,0+vi,0*wi,0; fi-1,j-vi,0-vi,1+vi,0*wi,0+vi,1*wi,1; fi-1,j-vi,0-v

11、i,2+vi,0*wi,0+vi,2*wi,2; fi-1,j-vi,0-vi,1-vi,2+vi,0*wi,0+vi,1*wi,1+vi,2*wi,2; 很顯然時間復雜度為O(n2)，空間復雜度為O(n2)，加上利用“每件物品都是10元的整數(shù)倍”除以10的優(yōu)化，本題就很完美的解決了。（附程序）；program Qi(input,output);type node=record u:integer; v:array0.2 of integer; p:array0.2 of integer; end;var n,m,k:integer; w:array1.60 of node; f:array0

12、.60,0.3200 of longint; g:array1.60 of integer;procedure init; var i,j:integer; vx,px,qx:array1.60 of integer; begin readln(n,m); k:=0; for i:=1 to m do begin readln(vx,px,qx); if qx=0 then begin k:=k+1; g:=k; with wk do begin u:=0; v0:=vx; p0:=px; for j:=1 to 2 do begin vj:=0; pj:=0; end; end; end;

13、end; for i:=1 to m do if qx0 then begin with wgqx do begin u:=u+1; v:=vx; p:=px; end; end; for i:=1 to k do with w do begin for j:=0 to 2 do write(,vj,pj,); writeln; end; end;procedure doit; var i,j:integer; begin fillchar(f,sizeof(f),0); for i:=1 to k do with w do begin for j:=1 to n do begin fi,j:

14、=fi-1,j; if (j=v0) and (fi,j=v0+v1) and (fi,j=v0+v2) and (fi,j=v0+v1+v2) and (fi,jfi-1,j-v0-v1-v2+v0*p0+v1*p1+v2*p2) then fi,j:=fi-1,j-v0-v1-v2+v0*p0+v1*p1+v2*p2; end; end; end;procedure print; begin writeln(fk,n); end;begin init; doit; print;end.作業(yè)調度方案對本題的評價：題目超長，超簡單，失分率最高。當我在考場上拿到這個題目的時候，考試的緊張的氣氛壓

15、抑著讀了一遍，不知所云，又讀了一遍，依然莫名其妙，讀第三便，Igiveup !考試回來，一看，這樣的題目竟然不會，一定是氣的死去活來，我就是這樣郁悶了整整的一個月的。超簡單的貪心算法。簡單的說：有n個工件要在m個機器上加工，每個工件都有m到工序，每個工序對應著相應的加工機器。一個工件的工序必須依次進行。同一臺機器同時只能加工一個工件。每個工件的每個工序需要一定的加工時間。問：加工完所有的工件需要的最少時間是多少？本題在題目中連算法都給出了，考察的是對題意的理解和數(shù)據(jù)結構，但本題的規(guī)模并沒有對數(shù)據(jù)結構做過高的要求。應該可以說是本次考試的最簡單的題目了，但不是送分題，很多人和我一樣都望而止步了。最

16、簡單，按部就班就可以了。下面是題目中給我們的詳盡算法：“當一個操作插入到某臺機器的某個空檔時（機器上最后的尚未安排操作的部分也可以看作一個空檔），可以靠前插入，也可以靠后或居中插入。為了使問題簡單一些，我們約定：在保證約束條件（1）（2）的條件下，盡量靠前插入。并且，我們還約定，如果有多個空檔可以插入，就在保證約束條件（1）（2）的條件下，插入到最前面的一個空檔?！苯ㄗh大家在考試的時候使用數(shù)組，平時可以用指針寫一寫（附程序）；program Qi(input,output);var m,n:integer; a:array1.400 of integer; f:array1.20,0.1000

17、 of boolean; wu,ti:array1.20,1.20 of integer; g,time:array1.20 of integer;procedure init; var i,j:integer; begin readln(m,n); for i:=1 to n*m do read(a); readln; for i:=1 to n do begin for j:=1 to m do read(wui,j); readln; end; for i:=1 to n do begin for j:=1 to m do read(tii,j); readln; end; end;pr

18、ocedure doit; var i,j,k,xtime:integer; begin fillchar(f,sizeof(f),true); fillchar(time,sizeof(time),0); fillchar(g,sizeof(g),0); for i:=1 to n*m do begin inc(ga); j:=timea+1; xtime:=0; while xtimetia,ga do begin if fwua,ga,j then inc(xtime) else xtime:=0; j:=j+1; end; timea:=j-1; for k:=j-xtime to j

19、-1 do fwua,ga,k:=false; end; end;procedure print; var i,j,best:integer; begin best:=0; for i:=1 to m do for j:=1000 downto 0 do if not fi,j then begin if bestj then best:=j; break; end; writeln(best); end;begin init; doit; print;end.備注：不知道為什么第6個數(shù)據(jù)我的答案是112.而提供的答案是116.?如果有錯.歡迎牛人指出.呵呵.(我的qq:418539455);

20、備注：2k進制數(shù)這就是傳說中的數(shù)學題嗎?考試前曾沸沸揚揚的流傳過這么一段：“今年的題目出于一數(shù)學教授，都是寫超難的題目，四個題目有三個是數(shù)學題。”再加上今年的maths庫函數(shù)登上歷史舞臺。更讓人深信不移：今年要考數(shù)學題。謠言不可信啊，冤死了多少牛們說本題是數(shù)學題，到不如說是個找規(guī)律的題目。我們還是用標準的數(shù)學方法做一下好了。本題其實就是個很簡單的組合數(shù)學問題。沒上過高三做不出也就算了，上過高三的牛們沒做出來，多為放棄的了。從題中可以看出，w的值限制著首位的取值。所以我們要對與特殊考慮。比如樣例中的w=7，就限制了首位只能取和。下面關心的就是位數(shù)的問題了，w決定了數(shù)的最大的位數(shù)，最少的位數(shù)要求是

21、位。k決定了數(shù)的位權。抽象的是說了半天也不說不清楚，舉個例子吧：就拿樣例說，k=3。所以位權是2k=8，w=7，決定了數(shù)的位數(shù)最大是w div k+1，最多位的數(shù)是最高位最大只能是2(w+1) mod k-1)-1。所以我們分兩種做討論：1.位數(shù)是最多位，2.位數(shù)小于最多位。1.位數(shù)為最多位（最多位為）；最高位位：后面的兩位只能在之間取兩個不同的數(shù)。顯然取法的種數(shù)為c2,6。cn,m=m!/(n!*(m-n)!)，就是組合數(shù)這里的最高位只能為，所以只討論一種情況。2.位數(shù)小于最多位。位：這兩位只能從之間取數(shù)，為c2,7。這里只有兩位的情況，所以只討論這一種情況。從上面的例子，我們可以看出一般的

22、情況：位權：n=2k。位數(shù)：l=w div k+1;當w mod k=0時，最高為最大為，結合下最高位最大值：2(w+1) mod k-1)-1。這是我們要知道的幾個基本的元素下面就是統(tǒng)計滿足的數(shù)的個數(shù)：1.位數(shù)為最多：最高為取值x (2=x=mhigh);對于給定最高位x都有一些L位滿足條件的數(shù)，這些數(shù)的個數(shù)為cl-1,n-x-1。：位數(shù)小于最多：對于每一個給定的w位數(shù)都對應著cw,n-1個滿足條件的數(shù)。把這些數(shù)的個數(shù)全部加起來就可以了。為了簡化算法，我們引進一個組合公式：cn,m=cn-1,m-1+cn,m-1;其中cn,m=m!/(n!*(m-n)! 如果不用高精度，int64可以過個點，高精度就可以全過了。(附程序);program Qi(input,output);var k,w,n,l,mhigh:integer; answer:array1.200 of integer; c:array1.512,1.512,1.100 of integer;procedure init; begin readln(k,w); end;procedure ready; var i,j,l,jin,s:integer; begin for