ACM动态规划问题简易模板(C++可编译)

1、0-1背包#includestdio.h#includestdlib.h//背包问题/*测试数据：输入：8238451667378334962输出：10101011*/intnum,c;intv[10];intw[10];intm[10][30];//设m[i][j],则表示在前i个物品中，背包大小是j的情况下，背包所装东西的最大价值voidknapsack(){intn=num-1;intjmax,i,j;if(w[n]c)jmax=w[n];elsejmax=c;for(i=0;ijmax;i++)m[n][i]=0;for(i=w[n];i=c;i++)m[n][i]=v[n];for(i=n-1;i0;i--){if(w[i]c)jmax=w[i];elsejmax=c;for(j=0;jjmax;j++)m[i][j]=m[i+1][j];for(j=w[i];j=c;j++){if(m[i+1][j]m[i+1][j-w[i]]+v[i])m[i][j]=m[i+1][j-w[i]]+v[i];elsem[i][j]=m[i+1][j];}}m[0][c]=m[1][c];if(c=w[0]){if(m[0][c]m[1][c-w[0]]+v[0])m[0][c]=m[1][c-w[0]]+v[0];}}voidtrackback(int*x){intn=num-1;inti;for(i=0;in;i++){if(m[i][c]==m[i+1][c])x[i]=0;else{x[i]=1;c=c-w[i];}}if(m[n][c]0)x[n]=1;elsex[n]=0;}intmain(){inti,x[10],j;scanf(%d%d,&num,&c);for(i=0;inum;i++)scanf(%d,&v[i]);for(i=0;inum;i++)scanf(%d,&w[i]);knapsack();for(i=0;i=c;i++)printf(%3d,i);printf(\n);for(i=0;inum;i++){for(j=0;j=c;j++)printf(%3d,m[i][j]);printf(\n);}trackback(x);for(i=0;inum;i++)printf(%d,x[i]);printf(\n);return0;}2、KMP算法#includeiostream#includestring.husingnamespacestd;inlinevoidBuildNext(constchar*pattern,size_tlength,unsignedint*next){unsignedinti,t;i=1;t=0;next[1]=0;while(ilength+1){while(t0&&pattern[i-1]!=pattern[t-1]){t=next[t];}++t;++i;if(pattern[i-1]==pattern[t-1]){next[i]=next[t];}else{next[i]=t;}}//pattern末尾的结束符控制，用于寻找目标字符串中的所有匹配结果用while(t0&&pattern[i-1]!=pattern[t-1]){t=next[t];}++t;++i;next[i]=t;}unsignedintKMP(constchar*text,size_ttext_length,constchar*pattern,size_tpattern_length,unsignedint*matches){unsignedinti,j,n;unsignedintnext[pattern_length+2];BuildNext(pattern,pattern_length,next);i=0;j=1;n=0;while(pattern_length+1-j=text_length-i){if(text[i]==pattern[j-1]){++i;++j;//发现匹配结果，将匹配子串的位置，加入结果if(j==pattern_length+1){matches[n++]=i-pattern_length;j=next[j];}}else{j=next[j];if(j==0){++i;++j;}}}//返回发现的匹配数returnn;}intmain(){chara[20],b[20];intn1,n2,n;unsignedintmatch[100];cina;n1=strlen(a);//待匹配串cinb;n2=strlen(b);//模板串n=KMP(a,n1,b,n2,match);coutnendl;for(inti=0;in;i++)coutmatch[i]'';}3、最大子段和#includeiostream#includestdio.husingnamespacestd;intmain(){intT,n;inta[50000];inthd[50000],tl[50000];scanf(%d,&T);while(T--){scanf(%d,&n);inti,temp,max;;for(i=0;in;i++)scanf(%d,&a[i]);//hd[],left-rightmax=hd[0]=a[0];for(i=1;in;i++){temp=a[i]+hd[i-1];hd[i]=tempa[i]?temp:a[i];}for(i=1;in;i++){hd[i]=maxhd[i]?max:hd[i];max=hd[i];}//tl[],right-leftmax=tl[n-1]=a[n-1];for(i=n-2;i=0;i--){temp=a[i]+tl[i+1];tl[i]=tempa[i]?temp:a[i];}for(i=n-2;i=0;i--){tl[i]=maxtl[i]?max:tl[i];max=tl[i];}max=hd[0]+tl[1];for(i=1;in-1;i++){temp=hd[i]+tl[i+1];max=maxtemp?max:temp;}printf(%d\n,max);}return0;}4、最长公共子序列（不严格连续）#includestdio.h#includestring.h#defineMAXLEN100voidLCSLength(char*x,char*y,intm,intn,intc[][MAXLEN],intb[][MAXLEN]){inti,j;for(i=0;i=m;i++)c[i][0]=0;for(j=1;j=n;j++)c[0][j]=0;for(i=1;i=m;i++){for(j=1;j=n;j++){if(x[i-1]==y[j-1]){c[i][j]=c[i-1][j-1]+1;b[i][j]=0;}elseif(c[i-1][j]=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=1;}else{c[i][j]=c[i][j-1];b[i][j]=-1;}}}}voidPrintLCS(intb[][MAXLEN],char*x,inti,intj){if(i==0||j==0)return;if(b[i][j]==0){PrintLCS(b,x,i-1,j-1);printf(%c,x[i-1]);}elseif(b[i][j]==1)PrintLCS(b,x,i-1,j);elsePrintLCS(b,x,i,j-1);}intmain(intargc,char**argv){charx[MAXLEN]={ABCBDAB};chary[MAXLEN]={BDCABA};intb[MAXLEN][MAXLEN];intc[MAXLEN][MAXLEN];intm,n;m=strlen(x);n=strlen(y);LCSLength(x,y,m,n,c,b);PrintLCS(b,x,m,n);return0;}5、最长公共子序列（不严格连续）#includeiostream#includecstdio#includememory.husingnamespacestd;constintN=505;intnum1[N],num2[N],f[N][N];intmain(){intt,n,m;scanf(%d,&t);while(t--){scanf(%d,&n);for(inti=1;i=n;i++)scanf(%d,&num1[i]);scanf(%d,&m);for(intj=1;j=m;j++)scanf(%d,&num2[j]);memset(f,0,sizeof(f));intanswer=0;intma;for(inti=1;i=n;i++){ma=0;for(intj=1;j=m;j++){f[i][j]=f[i-1][j];if(num1[i]num2[j]&&f[i-1][j]ma)ma=f[i-1][j];if(num1[i]==num2[j])f[i][j]=ma+1;}}for(intj=0;j=m;j++)answer=max(answer,f[n][j]);printf(%d\n,answer);if(t!=0)printf(\n);}return0;}6、最大子矩阵和#includeiostream#includememory.husingnamespacestd;//求最大连续子矩阵和，动态规划，O(n^3)oftime:/*输入41-43-8-352-32-181-11-2-4输出14*/intmax_sum(intn,int*arr){//求单个序列的最大连续子串和intresult=0;intb=0;for(inti=0;in;i++){if(b0)b+=arr[i];elseb=arr[i];if(bresult)result=b;}returnresult;}intmax_sum2(intm,intn,int**arr){intresult=0;int*b=newint[n];for(inti=0;im;i++){memset(b,0,sizeof(int)*n);for(intj=i;jm;j++){for(intk=0;kn;k++)b[k]+=arr[j][k];//b[k]=arr[i][k]+arr[i+1][k]+...+arr[j][k]//从例子来说，当i=1,j=2时，有b[k]=arr[1][k]+arr[2][k],这时取到maxintmax=max_sum(n,b);if(maxresult)result=max;}}deleteb;returnresult;}intmain(){intN;cinN;inti,j;int**arr=newint*[N];for(i=0;iN;i++){arr[i]=newint[N];for(j=0;jN;j++)cinarr[i][j];}coutmax_sum2(N,N,arr)endl;for(i=0;iN;i++)deletearr[i];deletearr;return0;}7、石子合并问题#includeiostream#includestdio.husingnamespacestd;//石头合并问题PKU1086动态规划/*输入：44123输出：*/#defineMAX1000000000inta[202];//每个石头的重量longf[202][202];//f[i][j]，第i个石头分到第j个石头合并的最小代价longsum[202][202];//sum[i][j],第i个石头到第j个石头的重量之和voidprint(intnum