1、算法設(shè)計(jì)與分析實(shí)驗(yàn)報告實(shí)驗(yàn)二 遞歸與分治策略報告書姓名指導(dǎo)教師學(xué)號日 期班級實(shí)驗(yàn)內(nèi)容1）都說天上不會掉餡餅，但有一天gameboy正走在回家的小徑上，忽然天上掉下大 把大把的餡餅。這餡餅別處都不掉，就掉落在他身旁的10米范圍內(nèi)。餡餅如果掉在 了地上當(dāng)然就不能吃了，所以gameboy馬上卸下身上的背包去接。但由于小徑兩側(cè) 都不能站人，所以他只能在小徑上接。由于gameboy平時老呆在房間里玩游戲，雖 然在游戲中是個身手敏捷的高手，但在現(xiàn)實(shí)中運(yùn)動神經(jīng)特別遲鈍，每秒種只有在移 動不超過一米的范圍內(nèi)接住墜落的餡餅。為了使問題簡化，假設(shè)在接下來的一段時 間里，餡餅都掉落在0-10這11個位置。開始時ga

2、meboy站在5這個位置，因此在 第一秒，他只能接到4,5,6這三個位置中期中一個位置上的餡餅。問gameboy最多 可能接到多少個餡餅？（假設(shè)他的背包可以容納無窮多個餡餅）請自行設(shè)定輸入輸 出和測試數(shù)據(jù)。實(shí)驗(yàn)?zāi)康?）了解動態(tài)規(guī)劃的用法。實(shí)驗(yàn)過程和步驟Module 1:免費(fèi)餡餅Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 59327 Accepted Submission(s): 20813Problem Description都說天上不

3、會掉餡餅，但有一天gameboy正走在回家的小徑上，忽然天上掉下大把 大把的餡餅。說來gameboy的人品實(shí)在是太好了，這餡餅別處都不掉，就掉落在他身旁 的10米范圍內(nèi)。餡餅如果掉在了地上當(dāng)然就不能吃了，所以gameboy馬上卸下身上的背 包去接。但由于小徑兩側(cè)都不能站人，所以他只能在小徑上接。由于gameboy平時老呆 在房間里玩游戲，雖然在游戲中是個身手敏捷的高手，但在現(xiàn)實(shí)中運(yùn)動神經(jīng)特別遲鈍， 每秒種只有在移動不超過一米的范圍內(nèi)接住墜落的餡餅。現(xiàn)在給這條小徑如圖標(biāo)上坐標(biāo):I I I I I * I I I I IU12345 El78910為了使問題簡化，假設(shè)在接下來的一段時間里，餡餅都掉

4、落在0-10這11個位置。開始時 gameboy站在5這個位置，因此在第一秒，他只能接到4,5,6這三個位置中其中一個位置 上的餡餅。問gameboy最多可能接到多少個餡餅？(假設(shè)他的背包可以容納無窮多個餡 餅)Input輸入數(shù)據(jù)有多組。每組數(shù)據(jù)的第一行為以正整數(shù)n(0n100000)，表示有n個餡餅掉 在這條小徑上。在結(jié)下來的n行中，每行有兩個整數(shù)x,T(0T100000),表示在第T秒有一 個餡餅掉在x點(diǎn)上。同一秒鐘在同一點(diǎn)上可能掉下多個餡餅。n=0時輸入結(jié)束。Output每一組輸入數(shù)據(jù)對應(yīng)一行輸出。輸出一個整數(shù)m，表示gameboy最多可能接到m個 餡餅。提示：本題的輸入數(shù)據(jù)量比較大，建

5、議用scanf讀入，用cin可能會超時。Sample Input614 1 TOC o 1-5 h z 12230Sample Output4代碼：#includecstdio”#includecstring”#includealgorithm”using namespace std;#define inf 100009#define loop(x,y,z) for(x=y;xz;x+)#define INF 99999999#define ll long longint n,maxTime;int ans;/輸出答案int rollcakeinf15;/rollcakeij表示i秒j位置可以

6、收集到的餡餅的個 數(shù)int dpinf15;/dij表示i秒如果站在j位置可以在i秒前，最多收集到 dij個餡餅void init()memset(rollcake,0,sizeof rollcake);memset(dp,0,sizeof dp);ans=0;maxTime=0;/輸入的最大時間bool isIllegal(int i) /判斷越界if(i10)return false;return true;int max(int a,int b,int c)a=ab?a:b;return ac?a:c;void calAns()/遞推int i,j;dp14=rollcake15;dp1

7、5=rollcake15;dp16=rollcake15;loop(i,2,maxTime+1)loop(j,0,11)/不會走到0點(diǎn)和10點(diǎn)的，但是可以走dpij=dpi-1j;if(isIllegal(j-1)&dpi-1j-1dpij)dpij=dpi-1j-1;if(isIllegal(j+1)&dpi-1j+1dpij)dpij=dpi-1j+1;dpij+=rollcakeij;loop(i,0,11)if(dpmaxTimeians)ans=dpmaxTimei;int main()int i,j;int pos,time;while(scanf(%d”,&n)if(n=0)break;init();/初始化loop(i,0,n)/輸入scanf(%d%d”,&pos,&time);rollcaketimepos+;if(timemaxTime)maxTi