cc动态规划与递推教程.ppt

OnlineJudge例题讲解,南开ACM协会,1002:NKPC1Lucy的难题,f(n)当n=50025002的时候，f(n)=n-5；当n50025002的时候，f(n)=f(f(n+2005)。现在请您试试编程解决Lucy的难题！初步想法：intf(intn)if(n递归化为循环用m表示f的层数，f(m,n)表示参数n嵌套了m层f，例如f(3,n)=f(f(f(n)f(1,n)=f(n)f(0,n)=n,while(1=scanf(%d,1002:NKPC1Lucy的难题,进一步改进设k=50025002f(1,k)=f(2,k+2005)=f(1,k+2000)也即f(k)=f(k+2000)设k+2005*m=50025002时有f(1,k)=f(1,k+2000),1002:NKPC1Lucy的难题,当k+2005*(m+1)=50025002时f(1,k)=f(2,k+2005)=f(2,k+2005+2000*t)=f(1,k+2000*(t+1)进一步可知f(k)=f(k+2000)仍然成立这样得到一个简单的方法，如果n=0a=0,1023:A+B+C+D+.的挑战,也可以利用cin.getline函数读入一整行，包括空格，或者gets函数也可以得到相同效果读入一整行之后，可以同样采取上述方法解题，但如果熟悉strtok函数的话实际上还有更好的做法，留作自学,1046:正整数划分问题,将一个正整数n表示成一系列正整数的和，如：N=n1+n2+nk（其中n1n2nk1，k1）正整数n的一个这种表示成为正整数n的一个划分。现在给出一个正整数n（80n1），求n的不同划分一共有多少种。,1046:正整数划分问题,假设n已经划分出一个数字为n1，则n-n1的划分成为一个子问题，因此可以考虑动态规划（DynamicProgramming=DP）但是n-n1的划分必须满足一个条件：划分出的最大数字不超过n1，因此我们可以设dpij表示将i进行划分，划分出的最大数字不超过j的种类,1046:正整数划分问题,初始值a1i=1,ai1=1(i=1)a0i=1(i=0)思考这里为什么不设为=0递推aij=sumai-kk/ji输出ann即可,a00=1;for(i=1;iN;+i)ai1=a1i=a0i=1;for(i=2;iN;+i)for(j=2;j=i;+j)for(k=1;k=i,OtherProblems,互动请说出你在OnlineJudge上面感兴趣的题目一起讨论,welcometoNKOJ,进入RanklistTop20并不困难每天来到NKOJ，体会AC的乐趣AC=AcceptedWA（哇）=WrongAnswerTLE=TimeLimitExceeded,NKPC介绍,也即南开大学程序设计竞赛我为程序狂每年四月举行，已举办三届中英文两版试题，英文试题早公布10道题目，10-14天时间，将代码提交到指定地址，不看代码内容，只根据测试数据打分，每个数据9分，10组全对另加10分颁发奖状、奖品计划下一届公开征题，针对低年级单独评奖,有奖解题,准备近期办一次有奖解题低年级单独评奖，奖品以算法相关书籍为主1-2题，难度不大，但需要花一点时间去写多参加ACM协会的活动有助于今后组队参