ACM第一次動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題算法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=算法總體思想動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多次。算法總體思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。算法總體思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)Thosewhocannotrememberthepastaredoomedtorepeatit.-----GeorgeSantayana,ThelifeofReason,BookI:IntroductionandReasoninCommonSense(1905)適用動(dòng)態(tài)規(guī)劃策略解決問(wèn)題特征最優(yōu)子結(jié)構(gòu)：一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過(guò)去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸多決策必須構(gòu)成最優(yōu)策略。簡(jiǎn)言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。無(wú)后向性某一階段一旦確定，就不受這個(gè)狀態(tài)以后決策的影響。子問(wèn)題重疊子問(wèn)題之間不獨(dú)立，一個(gè)子問(wèn)題在一下階段決策中可能多次使用到。動(dòng)態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解?！纠?】數(shù)塔hdu2084有如下所示的數(shù)塔，要求從頂層走到底層，若每一步只能走到相鄰的結(jié)點(diǎn)，則經(jīng)過(guò)的結(jié)點(diǎn)的數(shù)字之和最大是多少？

這道題如果用枚舉法（暴力思想），在數(shù)塔層數(shù)稍大的情況下（如31），則需要列舉出的路徑條數(shù)將是一個(gè)非常龐大的數(shù)目（2^30=1024^3>10^9=10億）。

拒絕暴力，倡導(dǎo)和諧～數(shù)組存放在a[N][N]里，下三角。自底向上即：

b[i][j]=a[i][j]+max{b[i+1][j],b[i+1][j+1]}。for(i=1;i<=6;i++)for(j=1;j<=i;j++)scanf("%d",&a[i][j]);for(i=1;i<=6;i++)b[6][i]=a[6][i];for(i=5;i>=1;i--)for(j=i;j>=1;j--) if(b[i+1][j]>b[i+1][j+1]) {b[i][j]=a[i][j]+b[i+1][j];} else {b[i][j]=a[i][j]+b[i+1][j+1];}printf(“%d\n”,b[1][1]);【例2】最大子段和(hdu1003)Description有一組數(shù),如-254-37的最大子段和是13,是從5到7.Input第一行輸入一個(gè)n(1<N<=100)表示這一組數(shù)有多長(zhǎng),第二行是N個(gè)數(shù).

測(cè)試案例有多個(gè),n=0時(shí)結(jié)束.Output輸出這一組數(shù)的最大子段和.SampleInput5-254-37109-38-2898-30-2050-24100SampleOutput1398最大子段和b[j]=b[j]=max(b[j-1]+a[j],a[j]},1<j<=nb[1]=a[1]#include<stdio.h>#defineN100inta[N];intmain(){ inti,n,b[N],max;while(scanf("%d",&n)&&n!=0){for(i=1;i<=n;i++) scanf("%d",&a[i]);b[1]=a[1];for(i=2;i<=n;i++) { if(b[i-1]>0) b[i]=b[i-1]+a[i]; else b[i]=a[i]; }max=b[1];for(i=1;i<=n;i++) if(max<b[i]) max=b[i]; printf("%d\n",max);} return0;}【例3】最長(zhǎng)上升子序列（或者非降子序列）

一個(gè)數(shù)的序列bi,當(dāng)b1<B2<B3....<BS的時(shí)候,稱這個(gè)序列是上升的。對(duì)于給定的一個(gè)序列(A1,A2,....,AN),可以得到一些上升的子序列(AI1,AI2,....AIK,這里1<=I1<=I2<....<IK<=N,比如,對(duì)于序列(1,7,3,5,9,4,8),有它的一些上升子序列,如(1,7),(3,4,8)等.這些子序列中最長(zhǎng)的長(zhǎng)度是4,比如子序列(1,3,5,8).

你的任務(wù)就是對(duì)于給定的序列,求出最長(zhǎng)上升子序列的長(zhǎng)度.數(shù)據(jù)存在a[N](0號(hào)末用）設(shè)置b[N]，b[i]表示序列的第1個(gè)數(shù)到第i個(gè)數(shù)（保留第i個(gè)數(shù)）的最長(zhǎng)上升子序列的長(zhǎng)度。b[i]=max(b[j])+1(a[j]<a[i],1<=j<=i<=n)如果a[i]最小，則b[i]=1#include<stdio.h>intA[100],B[100];intmain(){ intn,i,j,max; while(scanf("%d",&n)!=EOF) { for(i=0;i<n;i++) scanf("%d",&A[i]); B[0]=1; for(i=1;i<n;i++) { max=0; for(j=0;j<i;j++) if(A[j]<A[i]&&B[j]>max)max=B[j]; B[i]=max+1;

} max=B[0]; for(i=1;i<n;i++) if(max<B[i])max=B[i]; printf("%d\n",max); } return0;}【例4】最長(zhǎng)公共子序列(杭電1159）我們稱序列Z=是序列X=的子序列當(dāng)且僅當(dāng)存在嚴(yán)格上升的序列,使得對(duì)j=1,2,...k,有Xi=Zj.比如Z=(a,b,f,c)是X=的子序列.現(xiàn)在給出兩個(gè)序列X和Y,任務(wù)是找到X和Y的最大公共子序列,也就是說(shuō)要找到一個(gè)最長(zhǎng)的序列Z,使得Z既是X的子序列也是Y的子序列.SampleInputabcfbcabfcabprogrammingcontestabcdmnpSampleOutput420Z[i][j]記錄X(i)和Y(j)的最大子序列的長(zhǎng)度Z[i][j]=#include<stdio.h>#include<string.h>charx[201];chary[201];intz[200][200];intmain(){inti,j,s,t,max;while(scanf("%s%s",x,y)!=EOF){s=strlen(x);t=strlen(y); for(i=0;i<s;i++) z[i][0]=0; for(j=0;j<t;j++) z[0][j]=0; for(i=1;i<=s;i++) for(j=1;j<=t;j++) { if(x[i-1]==y[j-1])z[i][j]=z[i-1][j-1]+1; else { if(z[i-1][j]>=z[i][j-1])z[i][j]=z[i-1][j]; elsez[i][j]=z[i][j-1]; } } printf("%d\n",z[s][t]);}

return0;}scanf(“%s%s”,a,b);la=strlen(a);lb=strlen(b);memset(c,0,sizeof(c));for(i=la-1;i>=0;i--)for(j=lb-1;j>=0;j--){

if(a[i]==b[j])c[i][j]=c[i+1][j+1]+1;elsec[i][j]=max(c[i+1][j],c[i][j+1]);}printf(“%d”,c[0][0]);背包（采藥）有n件物品和一個(gè)容量為c的背包。第i件物品的重量是w[i]，價(jià)值是v[i]。求解將哪些物品裝入背包可使這些物品的重量和不超過(guò)背包容量，且價(jià)值總和最大。輸出總價(jià)值。13010546845885671635648457798577536967257037110069112#include<stdio.h>#include<string.h>intg[100][1002];intmain(){inti,j,w,n,m,v; while(scanf("%d%d",&n,&m)!=EOF)//n為重量數(shù)，M為物品個(gè)數(shù)

{ memset(g,0,sizeof(g)); scanf("%d%d",&w,&v);//c為重量，V為價(jià)值

for(i=0;i<w;i++) g[1][i]=0; for(i=w;i<=n;i++) g[1][i]=v; for(i=2;i<=m;i++) { scanf("%d%d",&w,&v); for(j=0;j<=n;j++) { if(j<w) g[i][j]=g[i-1][j]; else if(g[i-1][j-w]+v>g[i-1][j]) g[i][j]=g[i-1][j-w]+v; else g[i][j]=g[i-1][j]; } } printf("%d\n",g[m][n]); }return0;}Palindrome描述所謂回文字符串，就是一個(gè)字符串，從左到右讀和從右到左讀是完全一樣的，比如"aba"。當(dāng)然，我們給你的問(wèn)題不會(huì)再簡(jiǎn)單到判斷一個(gè)字符串是不是回文字符串?，F(xiàn)在要求你，給你一個(gè)字符串，可在任意位置添加字符，最少再添加幾個(gè)字符，可以使這個(gè)字符串成為回文字符串。輸入第一行給出整數(shù)N（0<N<100）接下來(lái)的N行，每行一個(gè)字符串，每個(gè)字符串長(zhǎng)度不超過(guò)1000.輸出每行輸出所需添加的最少字符數(shù)樣例輸入1Ab3bd樣例輸出2定義d[i][j]為從字符i到字符j需要加入的字符的個(gè)數(shù)。#include<iostream>#include<fstream>usingnamespacestd;shortd[5001][5001];//如果不用short,可能會(huì)超內(nèi)存charstr[5005];intmin(intx,inty){if(x<y)returnx;elsereturny;}intmain(){ intw,n,i,j; scanf("%d",&w); while(w--) { scanf("%s",str); memset(d,0,sizeof(d)); n=strlen(str); for(i=n-1;i>=0;i--) for(j=i+1;j<=n-1;j++) { if(str[i]==str[j]) d[i][j]=d[i+1][j-1]; elsed[i][j]=min(d[i+1][j],d[i][j-1])+1; } printf("%d\n",d[0][n-1]); } return0;}免費(fèi)餡餅ProblemDescription都說(shuō)天上不會(huì)掉餡餅，但有一天gameboy正走在回家的小徑上，忽然天上掉下大把大把的餡餅。說(shuō)來(lái)gameboy的人品實(shí)在是