————————————————————————
?
我用了記憶化，因為它比DP更好理解
?
—————————————————————————
資料：百度百科（ MIKU,I Love HER ）
來自洛谷：（背包的題解）//侵權刪
?
——————————————————————————
?
分析：不會dp怎么辦，記憶化來代替
（oi籠罩在一片痛苦中，神說：讓dp誕生吧，oi更加痛苦了）
?
——————————————————————————
?
原題鏈接；P2690
?
—————————————————————————
?
代碼：↓
/* welcome這里是記憶化搜索，// 別問我是什么，我是蒟蒻 其實記憶化和動態規劃很像，真的很像，但是，記憶化比較好想畢竟它還是DFS */ #include<iostream> #include<cstdio> #include<cstring> using namespace std; int t,w;//總時間和總步數 int zong[100000];//蘋果位置 int dp[10000][100];//記憶化也 int dfs(int step,int now,int time){//既然是記憶化，就要把這些變量 全列上 if(time>t)//邊界——超時 return 0;if(-1!=dp[time][step]) return dp[time][step];//記憶部分 if(zong[time]==now)//蘋果在當前的樹上 return dp[time][step]=dfs(step,now,time+1)+1;//直接加一即可 else{if(step<w)//如果能動 return dp[time][step]=max(dfs(step+1,-1*now+3,time+1)+1,dfs(step,now,time+1));//就計算動和不動的最大值 elsereturn dp[time][step]=dfs(step,now,time+1); //動不了了 } }int main() {//初始化和讀入 memset(dp,-1,sizeof(dp));cin>>t>>w;for(int i=1;i<=t;++i)cin>>zong[i];cout<<dfs( 0,1,1); }
?
?
?
?
---恢復內容結束---
