網(wǎng)上找的一些動態(tài)

1、動態(tài)規(guī)劃題(擴充中)tju1004 防御題目：Problem某國為了防御敵國的，發(fā)展出一種系統(tǒng)。但是這種系統(tǒng)有一個缺陷：雖然它的第一發(fā) 彈能夠達到任意的高度，但是以后每一發(fā) 彈都不能高于前一發(fā)的高度。某天，捕捉到敵國的來襲。由于該系統(tǒng)還在使用階段，所以只有一套系統(tǒng)，因此有可能不能所有的。Input最多 20 個整數(shù)，分別表示依次飛來的高度（給出高度數(shù)據(jù)是不大于 30000的正整數(shù)）Output兩個整數(shù)M 和N。表示：這套系統(tǒng)最多能M套這種枚，如果要所有最少要配備 N系統(tǒng)。Sle Input300 250 275 252 200 138 245S5 2le Output算法：這道題就是典型的最長

2、單調(diào)序列和最長單調(diào)序列的覆蓋問題，兩個問題分別求。問題一：求最長單調(diào)序列的長度。設(shè)opti表示從 A1 到 Ai 的最長單調(diào)序列長度，則：opt1=1opti=maxoptk+1 (1=k=Ai)最后輸出 optn.問題二：最長單調(diào)序列的覆蓋個數(shù)可以不斷求出最長單調(diào)序列，把它們從序列集合中刪去，直到集合為空集，在此過程中進行累加。復(fù)雜度：方法的時間復(fù)雜度為o(n2)，tju1004 已經(jīng)可以 Accepted，但是如果 n1000000 時，速度顯然不如人意。改進：有沒有更好的方法呢？當(dāng)然有！最長單調(diào)序列，顧名思義，單調(diào)的，即：Ak= )Ai (ki)于是難道不可以只保存最后一個數(shù)？首先,開一

3、個足夠大的數(shù)組?A:array1.maxnof longAi表示長度為 i 的最長單調(diào)序列的最后一個數(shù)字，程序如下：procedure main; var .beginfillchar(a,sizeof(a),0); ans:=0; 最長單調(diào)序列的長 readln(n);for s:=1 to n do begin read(x);l:=1; r:=ans; 左、右范圍 whl=r do begin 二分m:=(l+r) shr 1;if amans then inc(ans); 新建，即長度為 ans+1 的最長單調(diào)序列出現(xiàn)了！ al:=x;end;end;最長單調(diào)序列的覆蓋個數(shù)也很好求，只

4、要將if am=x then l:=m+1 elser:=m-1 中的=即可，其它類似。算法的復(fù)雜度顯然降低了！疑問：為什么只要將 if am=x then l:=m+1 else r:=m-1 中的=即可？tju1039 核電站問題題目：Problem一個核電站有N 個放核物質(zhì)的坑，坑排列在一條直線上。如果連續(xù)M 個坑中放入核物質(zhì)，則會發(fā)生，于是，在某些坑中可能不放核物質(zhì)。任務(wù)：對于給定的N 和M，求不發(fā)生的放置核物質(zhì)的方案總數(shù)Input該題有多組測試數(shù)據(jù)，每組數(shù)據(jù)一行，兩個正整數(shù)N，M( 1N50，2M5)Output每組數(shù)據(jù)只輸出一個正整數(shù)S，表示方案總數(shù)。S4 3le InputSle

5、 Output13算法:這道題似乎可以用容斥定理來做，但要實現(xiàn)幾乎不可能，運算中的數(shù)據(jù)會很大，即使高精度也很慢很煩。很自然的想到了可以用動態(tài)規(guī)劃算法。開始試探兩個元素的 dp，設(shè):fi,j表示前 i 個坑放置j 個核物質(zhì)時的放置總方案數(shù)，那么似乎fi,j= fi-1,j-1當(dāng) j0在第i 個坑放核物質(zhì)不在第i 個坑放核物質(zhì)fi-1,j當(dāng)j=0但程序編好后,發(fā)現(xiàn)結(jié)果不對，因為有情況沒考慮到?如果在第 i 個坑放核物質(zhì)，那么也許前i-1 個坑里j-1 個核物質(zhì)放在最后連續(xù)j-1 個坑里，在這種情況下在第i 個坑放核物質(zhì)是不允許的！只好再增加一個參數(shù)k,fi,j,k表示前 i 個坑放置j 個核物質(zhì)且

6、最后連續(xù)放置k 個核物質(zhì)時的放置總方案數(shù)，那么fi,j,k= fi-1,j-1,k-1當(dāng)k0 fi-1,j,l 當(dāng) k=0最后用個二重循環(huán)統(tǒng)計一下，大功告成！復(fù)雜度：很顯然時間復(fù)雜度為o(n3)，空間復(fù)雜度為 o(n3)，使用滾動數(shù)組可降一維。疑問：雖然 dp 可以通過，但很可能有更好的算法（如公式），目前沒有找到，但有一發(fā)現(xiàn)：Ans(n,m)= 2n-omega當(dāng)n-m 不變，omega 為常數(shù)，問題是omega 與n-m 到底關(guān)系？tju1048 Tom 的煩惱題目：ProblemTom 是一個非常有創(chuàng)業(yè)精神的人，由于大學(xué)學(xué)的是汽車制造專業(yè)，所以畢業(yè)后他用有限的開了一家汽車零件，專門為汽車

7、制造商制造零件。由于有限，他只能先一臺加工機器?，F(xiàn)在他卻遇到了麻煩，多家汽車制造商需要他加工一些不同零件（由于廠家和零件不同，所以給的加工費也不同），而且不同廠家對于不同零件的加工時間要求不同（有些加工時間要求甚至是的，但開始和結(jié)束時間相同不算）。Tom 當(dāng)然希望能把所有的零件都加工完，以得到的加工費，但當(dāng)一些零件的加工時間要求有時，在某個時間內(nèi)他只能選擇某種零件加工（因為他只有一臺機器），為了賺得盡量多的加工費，Tom 不知如何進行取舍。現(xiàn)在請你幫Tom 設(shè)計一個程序，合理選擇部分（或全部）零件進行加工，使得得到最大的加工費。Input第一行是一個整數(shù) m,表示測試數(shù)據(jù)的個數(shù)。每組測試數(shù)據(jù)的

8、第一行是一個整數(shù)n(n=30000)，表示共有 n 個零件須加工。接下來的n 行中，每行有 3 個整數(shù)，分別表示每個零件加工的時間要求。第一個表示開始時間，第二個表示該零件加工的結(jié)束時間，第三個表示加工該零件可以得到的加工費。注：數(shù)據(jù)中的每個數(shù)值不會超過 100000.Output對每組測試數(shù)據(jù),輸出一個整數(shù)，表示 Tom 可以得到的最大加工費。Sle Input525Sle Output30算法：這一題要用動態(tài)規(guī)劃解決。設(shè)：fi表示到達時間 i 時所能得到的最大加工費，則：fi= maxfk-1+vk,i (0ki) 其中，(k,i)是輸入數(shù)據(jù)中給的一段時間,vk,i表示這段時間內(nèi)的加工費。

9、最后輸出 f30000即可。改進：首先，將結(jié)束時間作為關(guān)鍵字排序，至于數(shù)組 ai中，以便處理。隨后，在查找是否存在時間(k,i)時只需用一個指針來控制即可。復(fù)雜度：時間復(fù)雜度為 o(n2)，空間復(fù)雜度為 o(n)，全部數(shù)據(jù)能在 1s 內(nèi)通過！疑問：有沒有更好的算法呢？tju1049 砝碼問題題目：Problem有一組砝碼，重量互不相等，分別為 m1、m2、m3mn；它們可取的最大數(shù)量分別為 x1、x2、x3xn?，F(xiàn)要用這些砝碼去稱物體的重量,問能稱出多少種不同的重量。Input第一行為一整數(shù) t,表示有 t 組測試數(shù)據(jù)。每組測試數(shù)據(jù)第一行一個整數(shù)n（n=10），表示有多種不同的砝碼；第二行n

10、個整數(shù)（中間用空格分隔），m1、m2、m3mn，分別表示 n 個砝碼的重量；（1=mi=20）第三行n 個整數(shù)（中間用空格分隔），x1、x2、x3xn，分別表示 n 個砝碼可取的最大數(shù)量。（1=xi=20）Output每組數(shù)據(jù)輸出僅一行，一個整數(shù)，表示利用給定的砝碼可以稱出的不同的重量數(shù)。注：包括 0。S 121 22 1le InputS5le Output算法：看到這道題很容易聯(lián)想到典型的背包問題，只是有一點變化。設(shè)：型的 fi,j表示前 i 個砝碼能否稱出重量j，則：f0,0:=truefi,j:=fi,j or fi-1,j-k*mi (1=k=0)最后用個一重循環(huán)統(tǒng)計一下 fn,p(

11、0=p=maxm)有多少個值為 true 的即可。改進：空間不夠時可以用滾動數(shù)組來降一維，其實不只如此。不僅要注意到第i 個狀態(tài)只與第i-1 個狀態(tài)有關(guān)，還可以發(fā)現(xiàn)j-k*mij!所以連滾動數(shù)組都不需要，只需直接用一個數(shù)組從頭到尾一下！復(fù)雜度：經(jīng)過優(yōu)化，時間復(fù)雜度為o(n2)，空間復(fù)雜度為 o(n)，應(yīng)該比較理想。tju1050 單詞的劃分題目：Problem有一個很長的由小寫字母組成字符串。為了便于對這個字符串進行分析，需要將它劃分成若干個部分，每個部分稱為一個單詞。出于減少分析量的目的，希望劃分出的單詞數(shù)越少越好。你就是來完成這一劃分工作的。Input第一行為一整數(shù)T，表示有T 組測試數(shù)據(jù)

12、。每組測試數(shù)據(jù)第一行為一字符串。(長度小于 256)第二行為一整數(shù)N。（1=N=100）以下N 行，每行一個單詞。Output一個整數(shù)，表示字符串可以被劃分成的最少的單詞數(shù)。S1le Inputrealityour 5real reality it yourourS2le Output算法：這道題比較容易能想到用dijkstra 來求最短路徑，有另一種的方法?動態(tài)規(guī)劃。（其實，這里的動態(tài)規(guī)劃也可以理解為在求最短路徑）首先，用類似鄰接矩陣的型的li,j表示從 i 到j(luò) 是不是單詞。設(shè)：fi表示前i 個串能分成的最少單詞數(shù)，很簡單地得到：f0= 0fi= minfk+1 (0=ki)&(從 k+1

13、 到j(luò) 是單詞)（默認(rèn)從 0 到 0 是單詞）改進：可以像tju1048 Tom 的煩惱那樣，先排一下序再 dp。想必不用具體闡述了。復(fù)雜度：經(jīng)過優(yōu)化的時間復(fù)雜度為o(n2)，可以 Accepted。tju1059 數(shù)的計數(shù)題目：Problem先輸入一個自然數(shù)n(n3000000)，然后對此自然數(shù)按照如下方法進行處理1?不作任何處理:2?在它的左邊加上一個自然數(shù)，但該自然數(shù)過原數(shù)的一半;3?加上數(shù)后，繼續(xù)按此規(guī)則進行處理，直到不能再而 自然數(shù)為止。例如 n=66162612636136所以滿足要求的個數(shù)為 6。Input包含多個測試數(shù)據(jù),每行是一個整數(shù) n(1=n=3000000)Output

14、一個整數(shù),表示解的個數(shù)(保證不超過 50 位)S6le InputS6le Output算法：這道題在許多書上都有介紹，設(shè)：fi表示 i 個數(shù)的f1= 1，則：fi= fk改進 1：算法雖然經(jīng)典，但時間復(fù)雜度為 o(n2)，如此大的數(shù)據(jù)顯然要超時，能不能降低一維呢？換一種構(gòu)造就行了！假如g1 =1設(shè)gi表示 f1到 fi總和，那么gi =gi-1+gi|2時間復(fù)雜度降到了 1 維！ans1= 1ansi= gi-gi-1改進 2：不難看出，在解出 gi后，gk(1=ki)都出來了，那么可以在程序的開頭做一下預(yù)處理，這是極大的優(yōu)化！改進 3：盡管時間降低到一維，但數(shù)據(jù)很大(保證不超過 50 位)

15、!于是不得不用高精度運算，但如果這樣，時間復(fù)雜度不就又二維了嗎？可以用壓縮數(shù)組來避免。即：每一位數(shù)的范圍由 0 到 9 擴大到 0 到 9999999，這樣 50位數(shù)最多只用 8 位，o(8n)與 o(n)相差不大。改進 4：盡管做了 3 次改進，但空間上還是需要優(yōu)化(1=n=3000000，開不到！)。發(fā)現(xiàn) ansi=gi-gi-1，將這個式子拆開，便是：ansi =gi-gi-1 =gi-1+gi|2-gi-1 =gi|2而(1=n=3000000)，所以在做預(yù)處理時只要把 1500000 以內(nèi)的只求出就行了！而空間上也只需開一個 1.1500000 的數(shù)組。經(jīng)過以上四步改進，最終 AC

16、了！復(fù)雜度：時間復(fù)雜度o(n)，空間復(fù)雜度 o(n)。疑問：本人將 f1= 1fi= fk進行重新構(gòu)造后得出了，如果用組合數(shù)學(xué)的方法解此遞推式，是否能更好呢？本人尚不清楚，但本題方法值得一珍藏！tju1063 硬幣題目:Problem知道即使是同一種面值的硬幣，它們的重量也有可能不一樣，因為它受到許多的影響，包括制造工藝和流程上的。但是任何一種面值的硬幣的重量總是處于某個特定范圍之內(nèi)。現(xiàn)在已知所有面值的硬幣的重量范圍。給定一堆硬幣的總重量，問這堆硬幣的總價值有多少種不同的可能。舉例：已知一角硬幣的重量在 19 到 21 之間，五角硬幣的重量在 40 到 43 之間。有一堆硬幣的總重量為 99。

17、則它可以由 4 個重量為 20，1 個重量為 19 的一角硬幣組成，其總價值為 5 角，也可以由 1 個重量為 42 的五角硬幣和 3 個重量為 19 的一角硬幣組成，其總價值為 8 角，再或者由 2 個重量為 40的五角硬幣和 1 個重量為 19 的一角硬幣組成，其總價值為 1 塊 1 角。因此這堆硬幣的總價值共有 3 種不同的可能。Input該題含有多組測試數(shù)據(jù)。每組測試數(shù)據(jù)第一行是一個整數(shù)w（10=w=100）表示所有硬幣的總重量。第二行是一個整數(shù)n（1=n=7）表示不同面值的硬幣總數(shù)。接下來n 行每行 3 個整數(shù)，依次表示硬幣的面值，最小可能重量和最大可能重量。硬幣面值不超過 50，最

18、小重量不低于 2，最大重量不高于 100。最大重量和最小重量之間的差距不超過 30。Output每組數(shù)據(jù)輸出僅包括一行表示這堆硬幣的總價值有多少種不同的可能性。Sle Input9921 19 215 40 43S3le Output算法：此題的動態(tài)規(guī)劃也不難，構(gòu)造是關(guān)鍵，的可能，那么：f0,0,0= true設(shè)：型的 fk,i,j表示前 k 項是否有總值為i 而總重為jfk,i,j= fk,i,j or fk-1,i-value,j-weight下面就不用再具體說了。tju1077題目：Problem貓認(rèn)為自己很強，于是找彩虹。彩虹接受了，兩人都有一定的血HP1、HP2。HP1 是貓的，HP

19、2 是彩虹的。他們也有一定力 AP1、AP2，AP1 是貓的，AP2 是彩虹的。當(dāng)進行HP21 AP11時，對方的 HP 減少自己的力，比如 HP12AP21，當(dāng)彩虹貓時，貓的 HP2（HP1）1（AP2）1?，F(xiàn)在兩個人對決很多回合，每回合不是貓彩虹，就是彩虹貓。求貓能贏彩虹的勝率。保留 4 位小數(shù)。Input該題含有多組測試數(shù)據(jù),每行為 HP1,HP2,AP1 和AP2 （1=HP1,HP2,AP1,AP2=32767）Output每組數(shù)據(jù)輸出一行，為貓贏彩虹勝率的值Sle Input2 1 1 1Sle Output75.0000算法：這道題雖然動態(tài)規(guī)劃不完備，但 tju 上過了。方程想必

20、人人會列，fi,j=0.5*(fi-1,j+fi,j-1)但動態(tài)規(guī)劃在這題中并不是最好的，更提倡用組合數(shù)學(xué)里的公式！疑問：什么樣的公式最好？tju1078 祝福題目：Problem得知antis 即將沉沒的消息以后，King 決定把他的人民送到安全的國外去。但是碼頭已經(jīng)廢棄很多很多年了。碼頭前有一個迷宮，國王的騎士只身闖入了這個迷宮騎士在迷宮的出口遇到了不明生物的！騎士因為是單獨，所以很快便招架不住了，他的大馬被打得奄奄一息（。）這個時候，迷宮中的兩座石像(一個是貓，一個是天使。（！)里放出了無數(shù)鋒利的刀片，把不明生物全部殺死，騎士當(dāng)場暈倒在地。等他醒來，發(fā)現(xiàn)馬已經(jīng)死了，手上多了一個戒指，上面寫著：“這個戒指會幫助你逃脫。它賦予了神奇的力量。有了它，每次移動如果是只要|x-x1|+|y-y1| (x1,y1)的移動！”(Angel 暗自想：還有這么心黑的)迷宮為n*m 的矩陣。騎士從(n,到(1,。問：在戒指的幫助下，騎士最少要多少步才能回到？在步數(shù)最少的前提下，總共有多少種辦法到達？注意，騎士不會傻到一直停留在原地不動。Input該題含有多組測試數(shù)據(jù),對于每組數(shù)據(jù), 第 1 行 3 個整數(shù)，n, m,(1=n,m=20)和 P(P=50)，分別代