ACM程序设计-东北林业大学 acm05

ACM程序设计东北林业大学陈宇[e-mail]2020/2/22今天你AC了吗？2020/2/23第6讲DP入门2020/2/24我校的ACM在线评测系统acm.nefu.edu.cn课件下载地址：acm.nefu.edu.cn/kj/acm05.ppt2020/2/25动态规划法的设计思想动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。2020/2/26原问题的解原问题……填表子问题1子问题2子问题n动态规划法的求解过程2020/2/27n=5时分治法计算斐波那契数的过程。F(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)F(1)F(0)F(1)F(0)F(1)F(0)例：计算斐波那契数：2)2()1(1100)(nnFnFnnnF2020/2/2801234567890112358132134动态规划法求解斐波那契数F(9)的填表过程：注意到，计算F(n)是以计算它的两个重叠子问题F(n-1)和F(n-2)的形式来表达的，所以，可以设计一张表填入n+1个F(n)的值。2020/2/29用动态规划法求解的问题具有特征：能够分解为相互重叠的若干子问题；满足最优性原理（也称最优子结构性质）：该问题的最优解中也包含着其子问题的最优解。（用反证法）分析问题是否满足最优性原理：1.先假设由问题的最优解导出的子问题的解不是最优的;2.然后再证明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。2020/2/210动态规划法设计算法一般分成三个阶段：（1）分段：将原问题分解为若干个相互重叠的子问题；（2）分析：分析问题是否满足最优性原理，找出动态规划函数的递推式；（3）求解：利用递推式自底向上计算，实现动态规划过程。动态规划法利用问题的最优性原理，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。2020/2/211例1斐波那契数列nefu85计算斐波那契数列的值！该数列为1123581321.........有多组数据，每组1行，用N表示，1=N=50。输出Fibonacci(N)的值!2020/2/212代码：intn;longlongfeibo[51];feibo[1]=1;feibo[2]=1;for(inti=3;i=50;i++)feibo[i]=feibo[i-1]+feibo[i-2];//打表while(cinn)coutfeibo[n]endl;2020/2/213用递归能做吗？longlongdata[51];longlongfblq(intn){if(n==1||n==2)return1;else{if(data[n]==0)data[n]=fblq(n-1)+fblq(n-2);//看看这个！只算1次！returndata[n];}}2020/2/214现在同学们在纸上计算下题：计算N!input有多组数据，每组一行，用N表示，0=N=20;output输出N！2020/2/215递归的代码：#includecstdlib#includeiostreamusingnamespacestd;longlongdata[21];longlongjc(intn){if(n==0||n==1)return1;if(data[n]==0)data[n]=n*jc(n-1);returndata[n];}intmain(intargc,char*argv[]){intn;memset(data,0,sizeof(data));while(cinn)coutjc(n)endl;system(PAUSE);returnEXIT_SUCCESS;}2020/2/216递推的代码：#includecstdlib#includeiostreamusingnamespacestd;intmain(intargc,char*argv[]){intn;longlongdata[51];memset(data,0,sizeof(data));data[0]=1;data[1]=1;for(inti=2;i=20;i++)data[i]=i*data[i-1];while(cinn)coutdata[n]endl;system(PAUSE);returnEXIT_SUCCESS;}2020/2/217Nefu20穿过街道一个城市的街道布局如下:从最左下方走到最右上方,每次只能往上或往右走,一共有多少种走法?2020/2/218input输入很多行行数,每行1个数字代表n的值,当n=0时结束(2=n=15)output输出对应每行n值的走法.2020/2/219sample_input121050sample_output261847562522020/2/220递归的代码：intf[100][100];intgetf(intx,inty){if(f[x][y]!=-1)returnf[x][y];intresult;if(x==0||y==0)result=1;elseresult=getf(x-1,y)+getf(x,y-1);f[x][y]=result;returnresult;}2020/2/221Main()intmain(intargc,char*argv[]){inti,j,n;memset(f,-1,sizeof(f));while(cinn){if(n==0)break;coutgetf(n,n)endl;}system(PAUSE);returnEXIT_SUCCESS;}2020/2/222其实这题递推的代码更短：intn;longlongdata[21][21];for(inti=0;i=20;i++){data[i][0]=1;//处理边界data[0][i]=1;//处理边界}for(intj=1;j=20;j++)for(intk=1;k=20;k++)data[j][k]=data[j-1][k]+data[j][k-1];//公式while(cinn&&n)coutdata[n][n]endl;2020/2/223经过上面的思考，回忆一下：HDU2041超级楼梯HDU2044小蜜蜂结论：都可以用DP来做，其实只要数据不重复，递推和递归就算DP了！2020/2/224例：数字三角形nefu17738810274445265给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。2020/2/225分析：7（7）3（10）8（15）8（18）1(max(10,15)+1=16)0(15)2(20)7(25)4(20)4(19)4(24)5(30)2(27)6(26)5(24)看明白了吧！方程式：1(max(10,15)+1=16)有啥感觉？inp[i][j]=inp[i-1][j]+inp[i-1][j-1];2020/2/226intdata[102][102];//输入放数据Intinp[102][102];//放数字和intn;while(cinn){memset(inp,0,sizeof(inp));memset(data,0,sizeof(data));2020/2/227for(inti=1;i=n;i++)for(intj=1;j=i;j++){cindata[i][j];if(i==1)inp[i][j]=data[i][j];elseinp[i][j]=max(inp[i-1][j],inp[i-1][j-1])+data[i][j];}2020/2/228找出最后1行的最大值，并输出之!inttmp=0;for(intk=1;k=n;k++)if(tmp=inp[n][k])tmp=inp[n][k];couttmpendl;2020/2/229WelcometoHDOJThankYou~