@[metaphysis](/user/333388)
by mot1ve @ 2020-09-27 21:12:24
@[wqy_03](/user/250699) 大佬您开始刷紫题了吗。。。我连蓝题做着都费劲。。。
by yewanxingkong @ 2020-09-27 21:22:30
@[yewanxingkong](/user/236970) 垃圾紫题 只不过我记忆化写炸了
by mot1ve @ 2020-09-27 21:30:34
@[yewanxingkong](/user/236970) 我黄题做着都费劲
by mot1ve @ 2020-09-27 21:30:51
@[wqy_03](/user/250699)
从您的代码中，我并未看到记忆化数组mem发挥了作用。一般来说，记忆化数组的作用是作为一个表格，存储已经解决的子问题的解，当后续再次遇到该子问题时，直接返回解，不需要再次进行求解，这样就提高了效率。
您的代码中记忆化数组mem是三维数组，表示当横坐标为x，纵坐标为y，剩余行走步数为k时的最小花费，那么在递推过程中，当再次遇到该状态时，就直接返回该状态所对应的解。
您再思考一下，将递归的出口、状态的转移、最后状态的返回值考虑清楚，重新编码试一下。
如果仍然有问题，我再帮您看看。
by metaphysis @ 2020-09-27 21:43:35
@[metaphysis](/user/333388) 确实 这写的没啥用 判断死循环的
不过感觉不是WA的原因？
by mot1ve @ 2020-09-27 21:57:06
@[wqy_03](/user/250699)
需要补油时要加上建油库所需费用C：
```
else if(res==0)//需要补油
{
dfs(x,y+1,sum+A+C,k-1);
dfs(x,y-1,sum+A+B+C,k-1);
dfs(x+1,y,sum+A+C,k-1);
dfs(x-1,y,sum+A+B+C,k-1);
}
```
更改后，样例输出正确。提交8个测试点4AC，4TLE。
仔细想了一下，本题不能使用动态规划，因为状态对应的图可以构成圈，导致不满足动态规划的无后效性。
可以建模为最短路径问题，使用Dijkstra算法解决。
by metaphysis @ 2020-09-27 23:58:48
@[wqy_03](/user/250699)
您可以先对记忆化搜索进行进一步的优化，看看能不能AC。
by metaphysis @ 2020-09-28 00:06:51
@[metaphysis](/user/333388) 好的1 谢谢
by mot1ve @ 2020-09-28 10:03:37
@[wqy_03](/user/250699) 应该是 如果没有油了 那么就不能进行移动，所以应该跳出，而不是再走一步awa
by koishi_offical @ 2021-01-06 12:49:35