资源描述：
《acmicpc编程基础_7》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ACM/ICPC编程基础第七节记忆化搜索ACM/ICPC编程基础课前的话•1、作业（见BBS）–实验记录册：–期末大作业：•2、下学期选课（见BBS）–下学期希望继续留在ACM/ICPC实践班的请于14，15周在创新实验学院网站上选课。选择下学期的实践课程。作业•1、DOJ1191–题目：石头和硬币石头和硬币•Description:–一个无聊的中午，古德拜和剑突然想到了一个游戏，由两个人玩。游戏开始时，剑手上有m个石头，和n个硬币，古德拜的手上没有任何东西。每一个回合，剑要么给古德拜石头，要么给古德拜硬币，如果给的是石头，那古德拜就直
2、接收下；如果给的是硬币，古德拜就要还给剑一个石头（这个石头不会再给古德拜，被剑藏起来了），若此时古德拜没有石头，那游戏结束，古德拜输。如果最后剑手上没有可以给的东西了（从古德拜手中收到的石头不能再给出），那古德拜胜。古德拜在想有多少种赢的可能，聪明的你能帮助他么？•Input:SampleInput:–有多组数据–第一行为一个整数N(1<=N<=1000),表示有多少组数据•1–接下来每一组数据为以下格式•55–mn(0<=m<=35,0<=n<=35)SampleOutput:•Output:•42–古德拜赢的总数递归思路•1、如何定
3、义状态–solve(intjs,intjy,intgs,intgy)表示•剑有js个石头，jy个硬币•古德拜有gs个石头，gy个硬币–时古德拜赢的可能的数目•2、边界条件–js<0或jy<0或gs<0时，solve＝0–js==0且jy==0时，solve=1•3、递归公式–solve(js,jy,gs,gy)=–solve(js-1,jy,gs+1,gy)+solve(js,jy-1,gs-1,gy+1);认为这篇代码能Accepted的请举手TimeLimitExceeded•约2^70。•TimeLimitExceeded•如何改
4、进我们的思路？记忆化搜索•大量的状态被多次计算，严重浪费时间。•每个状态只被计算一次。计算之后立即将它的结果保存下来。下一次当需要这个状态的值的时候，直接取出上次保存的结果。•如何知道solve(js,jy,gs,gy)是否被计算过？•data[js][jy][gs][gy]–如果为-1，表示它没有被计算过。执行递归，并将结果保存在data[js][jy][gs][gy]中。–如果不为-1，表示它已经被计算过。不执行递归，直接取出保存在data[js][jy][gs][gy]中的值返回。如何初始化•开始时，我们需要将data[js][j
5、y][gs][gy]全部赋值为-1，表示都没有被计算过。•我们还有更简单的方法•memset(data,-1,sizeof(data));••#include–#include//poj•void*memset(void*s,charch,unsignedn);•从地址s开始，n长度的内存的每个字节赋值为ch。–memset(data,0,sizeof(data));//正确–memset(data,1,sizeof(data));//错误本学期课程总结•由于最后一节课我计划讲一些比较复杂的内容，
6、所以提前做一部分内容的总结第一节第12页第二节第10页•O(log(n))10^(100000)•O(sqrt(n))10^16•O(n)10^8•O(n^2)10^4•O(n^3)10^2•O(2^n)30•O(N!)11第三节第5页•1、对代码进行编译，生成可执行程序。–如果编译错误，返回CompileError。•2、开始执行程序，开始计时，并且使用in文件对程序进行输入，并且监视程序的执行状态。–如果程序中途崩溃式退出，立即结束程序并返回RuntimeError。–如果计时超过规定时间，立即结束程序并返回TimeLimitExc
7、eeded。•3、将程序的输出保存在out文件中。–如果out文件超过限制大小，立即结束程序并返回OutputLimitExceeded。•4、将out文件与标准答案ans文件进行比对。–如果相差“空格”，“回车”，“制表符”等格式控制符，将返回PresentationError。–如果相差其它内容，将返回WrongAnswer。–如果out文件与ans文件完全一致，将返回Accepted。其它一些常见的问题•RuntimeError•PresentationError关于明年的校赛•一、组队•二、集训–周赛（周日下午）–讲周赛的题目（
8、周日晚上）
