网站制作过程简介,滨海做网站需要多少钱,12网站免费建站,濮阳网页设计———————————————————————— 我用了记忆化#xff0c;因为它比DP更好理解 ————————————————————————— 资料#xff1a;百度百科#xff08; MIKU,I Love HER #xff09; 来自洛谷#xff1a;#xff08;背包的题解因为它比DP更好理解 ————————————————————————— 资料百度百科 MIKU,I Love HER 来自洛谷背包的题解//侵权删 —————————————————————————— 分析不会dp怎么办记忆化来代替 oi笼罩在一片痛苦中神说让dp诞生吧oi更加痛苦了 —————————————————————————— 原题链接P2690 ————————————————————————— 代码↓ /*
welcome这里是记忆化搜索// 别问我是什么我是蒟蒻 其实记忆化和动态规划很像真的很像但是记忆化比较好想毕竟它还是DFS */
#includeiostream
#includecstdio
#includecstring
using namespace std;
int t,w;//总时间和总步数
int zong[100000];//苹果位置
int dp[10000][100];//记忆化也
int dfs(int step,int now,int time){//既然是记忆化就要把这些变量 全列上 if(timet)//边界——超时 return 0;if(-1!dp[time][step]) return dp[time][step];//记忆部分 if(zong[time]now)//苹果在当前的树上 return dp[time][step]dfs(step,now,time1)1;//直接加一即可 else{if(stepw)//如果能动 return dp[time][step]max(dfs(step1,-1*now3,time1)1,dfs(step,now,time1));//就计算动和不动的最大值 elsereturn dp[time][step]dfs(step,now,time1); //动不了了 }
}int main()
{//初始化和读入
memset(dp,-1,sizeof(dp));cintw;for(int i1;it;i)cinzong[i];coutdfs( 0,1,1);
} ---恢复内容结束---转载于:https://www.cnblogs.com/For-Miku/p/10846895.html
