動(dòng)態(tài)acm新手該看看的dp

1、動(dòng)態(tài)規(guī)劃Dynamic Programming唐陳興2007.12.30動(dòng)態(tài)規(guī)劃的基本思想動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。在這類問(wèn)題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解。動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題，經(jīng)分解得到子問(wèn)題往往不是互相獨(dú)立的。若用分治法來(lái)解這類問(wèn)題，則分解得到的子問(wèn)題數(shù)目太多，有些子問(wèn)題被重復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重

2、復(fù)計(jì)算，節(jié)省時(shí)間。我們可以用一個(gè)表來(lái)記錄所有已解的子問(wèn)題的答案。不管該子問(wèn)題以后是否被用到，只要它被計(jì)算過(guò)，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃法的基本思路。具體的動(dòng)態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。動(dòng)態(tài)規(guī)劃法一般步驟1、找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；2、遞歸地定義最優(yōu)值（寫出動(dòng)態(tài)規(guī)劃方程）；3、以自底向上的方式計(jì)算出最優(yōu)值；4、根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。步驟1-3是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟4可以省略，步驟3中記錄的信息也較少；若需要求出問(wèn)題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟4，步驟3中記錄的信息必須足夠多以便構(gòu)造最優(yōu)解。動(dòng)態(tài)規(guī)劃問(wèn)題的

3、特征動(dòng)態(tài)規(guī)劃算法的有效性依賴于問(wèn)題本身所具有的兩個(gè)重要性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問(wèn)題重疊性質(zhì)。1、最優(yōu)子結(jié)構(gòu)：當(dāng)問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解時(shí)，稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2、重疊子問(wèn)題：在用遞歸算法自頂向下解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問(wèn)題的重疊性質(zhì)，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，在以后盡可能多地利用這些子問(wèn)題的解。從一個(gè)簡(jiǎn)單的問(wèn)題入手FOJ1004 Number Triangle求人從頂端到底部,每次只能向左下右下走,最多能取得的值.數(shù)據(jù)規(guī)模: 行數(shù)1=R=1000 數(shù)塔中數(shù)值0.100如圖最優(yōu)解為

4、 7-3-8-7-5 =30從一個(gè)簡(jiǎn)單的問(wèn)題入手狀態(tài)表示 用aij表示第i行第j列的值。 用F(i,j)表示第i行第j列走到底部所能取得的最大值。而F(1,1)就是題目所求的答案。搜索源代碼#includeconst int M=1000+5;int aMM,n;inline int max(int x,int y) return xy?y:x; int f(int i,int j) if (i=n) return aij; else return aij+max(f(i+1,j),f(i+1,j+1); int main() int i,j; while(scanf(%d,&n)=1) fo

5、r(i=1;i=n;i+) for(j=1;j=i;j+) scanf(%d,&aij); printf(%dn,f(1,1); return 0; 從一個(gè)簡(jiǎn)單的問(wèn)題入手人每次從頂部往下走，都有2種選擇。如果搜索，到第n層的搜索量為為2n。1=n=1000，這種搜索量是從時(shí)間角度無(wú)法接受的。細(xì)心觀察，不難發(fā)現(xiàn)實(shí)際上做了很多重復(fù)的搜索。用動(dòng)態(tài)規(guī)劃思想解決減少重復(fù)計(jì)算：自底向上。狀態(tài)表示 用aij表示第i行第j列的值。 用Fij表示第i行第j列走到底部所能取得的最大值。而F11就是題目所求的答案。狀態(tài)轉(zhuǎn)移Fij=aij+max(Fi+1j,Fi+1j+1) 動(dòng)態(tài)規(guī)劃源代碼#includeconst

6、 int M=1000+5;int fMM,aMM;inline int max(int x,int y) return xy?y:x; int main() int i,j,n; while(scanf(%d,&n)=1) for(i=1;i=n;i+) for(j=1;j=i;j+) scanf(%d,&aij); for(j=1;j=1;i-) for(j=1;j=i;j+) fij=aij+max(fi+1j,fi+1j+1); printf(%dn,f11); return 0;記憶化搜索記憶化搜索：算法上依然是搜索的流程，但是搜索到的一些解用動(dòng)態(tài)規(guī)劃的那種思想和模式作一些保存。一般

7、說(shuō)來(lái)，動(dòng)態(tài)規(guī)劃總要遍歷所有的狀態(tài)，而搜索可以排除一些無(wú)效狀態(tài)。更重要的是搜索還可以剪枝，可能剪去大量不必要的狀態(tài)，因此在空間開(kāi)銷上往往比動(dòng)態(tài)規(guī)劃要低很多。記憶化算法在求解的時(shí)候還是按著自頂向下的順序，但是每求解一個(gè)狀態(tài)，就將它的解保存下來(lái)，以后再次遇到這個(gè)狀態(tài)的時(shí)候，就不必重新求解了。這種方法綜合了搜索和動(dòng)態(tài)規(guī)劃兩方面的優(yōu)點(diǎn)，因而還是很有實(shí)用價(jià)值的。 記憶化搜索動(dòng)態(tài)規(guī)劃不僅需要推出狀態(tài)轉(zhuǎn)移方程式，還要進(jìn)行拓?fù)渑判?。搜索相?duì)于動(dòng)態(tài)規(guī)劃最大的劣勢(shì)無(wú)非就是重復(fù)計(jì)算子結(jié)構(gòu)，所以我們?cè)谒阉鞯倪^(guò)程中，對(duì)于每一個(gè)子結(jié)構(gòu)只計(jì)算一次，之后保存到數(shù)組里，以后要用到的時(shí)候直接調(diào)用就可以了。記憶化搜索的實(shí)質(zhì)是動(dòng)態(tài)規(guī)劃

8、,效率也和動(dòng)態(tài)規(guī)劃接近，形式是搜索,簡(jiǎn)單直觀，代碼也容易編寫，不需要進(jìn)行什么拓?fù)渑判蛄??？梢詺w納為：記憶化搜索=搜索的形式+動(dòng)態(tài)規(guī)劃的思想數(shù)塔記憶化搜索源代碼#include#includeconst int M=1000+5;int aMM,n, ff MM;inline int max(int x,int y) return xy?y:x; int f(int i,int j) if (ffij!=-1) return ffij; if (i=n) return aij; else return ffij=aij+max(f(i+1,j),f(i+1,j+1); int main() in

9、t i,j; while(scanf(%d,&n)=1) for(i=1;i=n;i+) for(j=1;j=i;j+) scanf(%d,&aij); memset(ff,-1,sizeof(ff); printf(%dn,f(1,1); return 0;FOJ1320 Ones給一個(gè)整數(shù)n，要你找一個(gè)值為n的表達(dá)式，這個(gè)表達(dá)式只有1 + * ( ) 夠成。并且1不能連續(xù)，比如11+1就不合法。輸入n,(1=n=10000)輸出最少需要多少個(gè)1才能構(gòu)成表達(dá)式。樣例：n=2=1+1 ans=2 n=10=(1+1)*(1+1+1+1+1) ans=7Ones讓fi表示最少數(shù)量的1能夠表示i。

10、add: fi=fj+fi-j 0jimultiply: fi=fj+fi/j 0ji, i%j=0for(i=1;i=n;i+) fi=i; for(j=1;ji;j+) fi=min(fi,fj+fi-j); if (i%j=0) fi=min(fj+fi-j); O(n2) n=10000OnesHow to improve?For multiply, 1j*ji.fi=minfj+fi/j+fi%j 1j*jiO(n1.5) 1=n=10000n1.5=1,000,000 算法時(shí)間可以以計(jì)算機(jī)每秒執(zhí)行8,000,000語(yǔ)句進(jìn)行估算。Ones源代碼#include #includeint

11、 f10001;int main() int i,j,tmp,r; for(i=1;i=10000;i+) r=sqrt(i); fi=i; for(j=2;j=r;j+) tmp=fi%j+fj+fi/j; if(tmpfi) fi=tmp; while(scanf(%d,&i)!=EOF) printf(%dn,fi); return 0;FOJ1319 Blocks of Stones 經(jīng)典的石子歸并問(wèn)題有n (1=n7 1-8 分?jǐn)?shù)7+8=15合并方案二: 2 5 1-2 6-8 分?jǐn)?shù)6+8=14FOJ1319 Blocks of Stones狀態(tài)表示：用ai 表示初始時(shí)每堆石子的個(gè)數(shù)

12、。用si表示初始時(shí)從第1堆到第i堆石子的總和。用fij(i=j)表示從第i堆合并到第j堆的最小分?jǐn)?shù)。fij=minfi,k-1+fk,j+wi,j;wij=sumaiaj=sj-si-1;這樣枚舉是n3的。FOJ1319 Blocks of Stonesfij=minfi,k-1+fk,j+wi,j;改進(jìn)k的取值范圍： Let s(i,j)=maxk|arg minfi,j s(i,j-1)=k=s(i+1,j) O(n2)FOJ1319 Blocks of Stones 另外，F(xiàn)OJ1319可以交換任意兩個(gè)相鄰的石堆，這步可以通過(guò)O(n)的枚舉來(lái)實(shí)現(xiàn)。FOJ1348 Longest Orde

13、red Subsequence 最長(zhǎng)遞增子序列給一個(gè)序列，求它的一個(gè)最長(zhǎng)遞增子序列。遞增序列滿足：a1 a2 . aN 例如序列(1, 7, 3, 5, 9, 4, 8) 的遞增子序列有 (1, 7), (3, 4, 8) (1,3,4,8) 其中(1,3,4,8)為最長(zhǎng)遞增子序列。求給定的序列中最長(zhǎng)遞增子序列的長(zhǎng)度。（最長(zhǎng)遞增子序列未必唯一）O(n2)設(shè)fi表示：序列L中以ai為末元素的最長(zhǎng)遞增子序列的長(zhǎng)度。在求以ai為末元素的最長(zhǎng)遞增子序列時(shí)，找到所有序號(hào)在序列L前面且小于ai的元素aj，即ji且ajai。如果這樣的元素存在，那么對(duì)所有aj,都有一個(gè)以aj為末元素的最長(zhǎng)遞增子序列的長(zhǎng)度f(wàn)j

14、，把其中最大的fj選出來(lái)，那么fi就等于最大的fj加上1，即以ai為末元素的最長(zhǎng)遞增子序列，等于以使fj最大的那個(gè)aj為末元素的遞增子序列最末再加上ai；如果這樣的元素不存在，那么ai自身構(gòu)成一個(gè)長(zhǎng)度為1的以ai為末元素的遞增子序列。 樣例說(shuō)明：ai= 1, 7, 3, 5, 9, 4, 8fi= x, x, x, x, x, x, 1fi= x, x, x, x, x, 2, 1fi= x, x, x, x, 1, 2, 1fi= x, x, x, 2, 1, 2, 1fi= x, x, 3, 2, 1, 2, 1fi= x, 2, 3, 2, 1, 2, 1fi= 4, 2, 3, 2,

15、1, 2, 1#includeint main() int i,j,n,a1001,f1001,ans; while(scanf(%d,&n)!=EOF) for(i=1;i=1;i-) fi=1; for(j=i+1;j=n;j+) if (aiaj & fifj+1) fi=fj+1; ans=0; for(i=1;i=n;i+) if (ansfi) ans=fi; printf(%dn,ans); return 0;O(n*log(n)對(duì)算法的改進(jìn)在上述算法中，在計(jì)算每一個(gè)fi時(shí)，都要找出最大的fj(ji)來(lái)，由于fj沒(méi)有順序，只能順序查找滿足ajai最大的fj，如果能將讓fj有序，就

16、可以使用二分查找，這樣算法的時(shí)間復(fù)雜度就可能降到O(nlogn)。于是想到用一個(gè)數(shù)組b來(lái)存儲(chǔ)“子序列的”最大遞增子序列的最末元素，即有bfj = aj在計(jì)算fi時(shí)，在數(shù)組b中用二分查找法找到滿足ji且bfj=ajai的最大的j,并將bfj+1置為ai樣例說(shuō)明：ai= 1, 7, 3, 5, 9, 4, 8b=1b=1,7b=1,3b=1,3,5b=1,3,5,9b=1,3,4,9b=1,3,4,8/LIS 最長(zhǎng)遞增序列n*log(n)int LIS (int *a,int n)int ans,i,k,*b=new int n+1;bans=0=-0 x7fffffff;for(i=0;ians

17、) b+ans=ai; else if (bkai) bk=ai;delete b; return ans;源代碼FOJ1147 Tiling In how many ways can you tile a 2 x n rectangle by 2 x 1 or 2 x 2 tiles? Here is a sample tiling of a 2 x 17 rectangle. Input is a sequence of lines, each line containing an integer number 0 = n = 250. For each line of input, ou

18、tput one integer number in a separate line giving the number of possible tilings of a 2xn rectangle. 狀態(tài)表示：Fn表示2 x n的走道上鋪滿1 x 2， 2 x 2 的磚塊的方法數(shù)量考慮最后一塊磚和最后兩塊磚的放法，很容易寫出DP狀態(tài)轉(zhuǎn)移方程。Fi=Fi-1+Fi-2+Fi-2, 邊界：F0=F1=1;最后一塊1 x 2豎放:Fi-1最后兩塊1 x 2橫放:Fi-2最后放一塊 2 x 2的:Fi-2另外： n = 250，需要高精度FOJ1342 Tight Words Given is an

19、 alphabet 0, 1, . , k, 0 = k = 9 . We say that a word of length n over this alphabet is tight if any two neighbour digits in the word do not differ by more than 1. Input is a sequence of lines, each line contains two integer numbers k and n, 1 = n = 100. For each line of input, output the percentage

20、 of tight words of length n over the alphabet 0, 1, . , k with 5 fractional digits. FOJ1342 Tight Words緊密單詞：?jiǎn)卧~中任何相鄰位置的數(shù)字相差不超過(guò)1。長(zhǎng)度為n，由0.k組成的單詞中，緊密單詞的百分比。(1=n=100，0=k=9)例如k=2, n=2 的單詞共有(k+1)n=32=9個(gè)。其中緊密單詞有7個(gè)：00,01,10,11,12,21,22非緊密單詞有2個(gè)：02,20百分比為7/9=77.77778%FOJ1342 Tight Words長(zhǎng)度為n，由0.k組成的單詞共有(k+1)n 個(gè)

21、，(1=n=100，0=k=9)。枚舉所有的單詞顯然是不可能的。 O(k+1)*n)空間，O(k+1)*n)時(shí)間在使用數(shù)字0.k構(gòu)造單詞的條件下，F(xiàn)ij表示單詞長(zhǎng)度為i,以數(shù)字j為基本單詞產(chǎn)生的緊密單詞的百分比。Fi0=(Fi-1j+Fi-1j+1)/(k+1);Fij=(Fi-1j-1+Fi-1j+Fi-1j+1)/(k+1);Fik=(Fi-1j-1+Fi-1j+1)/(k+1);#include #include double f10010; double tot;int main() int i,j,k,n; while (scanf(%d %d,&k,&n)!=EOF) k+; me

22、mset(f,0,sizeof(f); for (i=0;ik;i+) f0i=100.0/k; for (i=1;in;i+) fi0=fi-10/k; for (j=1;jk;j+) fij+=(fi-1j+fi-1j-1)/k; for (j=0;jk-1;j+) fij+=fi-1j+1/k; tot=0; for (i=0;i1)，則由長(zhǎng)度為n-1的概率添加頭尾得到 tmp0=(f0+f1)/(k+1);tmpi=(fi-1+fi+fi+1)/(k+1);tmpk=(fk-1+fk)/(k+1);memcpy(f,tmp,sizeof(double)*(k+1);for(ans=0.

23、0,i=0;i=k;i+) ans+=fi; #include stdio.hint main()double f10,temp10,ans;int k,n,i,t; while(scanf(%d%d,&k,&n)!=EOF) for(i=0;i=k;i+) fi=100.0/(k+1);for(t=2;t=n;t+) temp0=(f0+f1)/(k+1); for(i=1;i=k-1;i+) tempi=(fi-1+fi+fi+1)/(k+1); tempk=(fk-1+fk)/(k+1); for(i=0;i=k;i+) fi=tempi;for(ans=0.0,i=0;i=k;i+)

24、ans+=fi;printf(%0.5lfn,ans);return 0;FOJ1559 Count Zeros 正整數(shù)可以表示為2進(jìn)制。計(jì)算1.2n中，這些正整數(shù)以2進(jìn)制表示時(shí)共有多少個(gè)0. (1=n111的過(guò)程，而10000還有右數(shù)第4的1沒(méi)有被計(jì)算過(guò)，所以結(jié)果還要加1。FOJ1523 A Version of Nim 可以用DP解決的一類博弈問(wèn)題問(wèn)題描述: 有4堆石子每堆最多9個(gè)，2個(gè)人輪流取石子，每次可以且必須取其中1堆的1-3個(gè)石子，取得最后一個(gè)石子的人失敗，假設(shè)雙方都采用最優(yōu)策略，問(wèn)先手勝敗。局面必?cái)【郑簾o(wú)論如何取石子，其子狀態(tài)都是必勝局。必勝局：存在一種或一種以上的取法，使得其子

25、狀態(tài)為必?cái)【帧?duì)于本題，典型的必?cái)【钟?1,0,0,0),(5,0,0,0) 必勝局有(2,0,0,0),(3,0,0,0),(4,0,0,0),(1,1,0,0)FOJ1523 A Version of Nim四堆石子(x,y,i,j)Fxyij=1表示先手必勝，0表示先手必?cái)　f (x=0 & y=0 & i=0 & j=0) Fijxy=1; if (!ff(i-1,j,x,y) | !ff(i-2,j,x,y) | !ff(i-3,j,x,y)| !ff(i,j-1,x,y) | !ff(i,j-2,x,y) | !ff(i,j-3,x,y)| !ff(i,j,x-1,y) | !f

26、f(i,j,x-2,y) | !ff(i,j,x-3,y)| !ff(i,j,x,y-1) | !ff(i,j,x,y-2) | !ff(i,j,x,y-3) Fijxy=1;else Fijxy=0;int ff(int i,int j,int x,int y)if (i0 | j0 | x0 | y0) return 1;else return fijxy;FOJ1381 Regular ExpressionsYou are given two regular expressions R1 and R2 and should find minimal string S matching both. String consists of capi