ACM第一次动态规划

动态规划动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=算法总体思想动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。算法总体思想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)如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。算法总体思想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)适用动态规划策略解决问题特征最优子结构：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸多决策必须构成最优策略。简言之，一个最优化策略的子策略总是最优的。无后向性某一阶段一旦确定，就不受这个状态以后决策的影响。子问题重叠子问题之间不独立，一个子问题在一下阶段决策中可能多次使用到。动态规划基本步骤找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。【例1】数塔hdu2084有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如31），则需要列举出的路径条数将是一个非常庞大的数目（2^30=1024^3>10^9=10亿）。

拒绝暴力，倡导和谐～数组存放在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有一组数,如-254-37的最大子段和是13,是从5到7.Input第一行输入一个n(1<N<=100)表示这一组数有多长,第二行是N个数.

测试案例有多个,n=0时结束.Output输出这一组数的最大子段和.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】最长上升子序列（或者非降子序列）

一个数的序列bi,当b1<B2<B3....<BS的时候,称这个序列是上升的。对于给定的一个序列(A1,A2,....,AN),可以得到一些上升的子序列(AI1,AI2,....AIK,这里1<=I1<=I2<....<IK<=N,比如,对于序列(1,7,3,5,9,4,8),有它的一些上升子序列,如(1,7),(3,4,8)等.这些子序列中最长的长度是4,比如子序列(1,3,5,8).

你的任务就是对于给定的序列,求出最长上升子序列的长度.数据存在a[N](0号末用）设置b[N]，b[i]表示序列的第1个数到第i个数（保留第i个数）的最长上升子序列的长度。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】最长公共子序列(杭电1159）我们称序列Z=是序列X=的子序列当且仅当存在严格上升的序列,使得对j=1,2,...k,有Xi=Zj.比如Z=(a,b,f,c)是X=的子序列.现在给出两个序列X和Y,任务是找到X和Y的最大公共子序列,也就是说要找到一个最长的序列Z,使得Z既是X的子序列也是Y的子序列.SampleInputabcfbcabfcabprogrammingcontestabcdmnpSampleOutput420Z[i][j]记录X(i)和Y(j)的最大子序列的长度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件物品和一个容量为c的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量和不超过背包容量，且价值总和最大。输出总价值。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为重量数，M为物品个数

{ memset(g,0,sizeof(g)); scanf("%d%d",&w,&v);//c为重量，V为价值

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描述所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，比如"aba"。当然，我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你，给你一个字符串，可在任意位置添加字符，最少再添加几个字符，可以使这个字符串成为回文字符串。输入第一行给出整数N（0<N<100）接下来的N行，每行一个字符串，每个字符串长度不超过1000.输出每行输出所需添加的最少字符数样例输入1Ab3bd样例输出2定义d[i][j]为从字符i到字符j需要加入的字符的个数。#include<iostream>#include<fstream>usingnamespacestd;shortd[5001][5001];//如果不用short,可能会超内存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;}免费馅饼ProblemDescription都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是