ABC344F 题解

__vector__ · 2024-03-14 20:05:49 · 题解

题外话

代码量挺大，赛时没想到思路，会了思路后写了半个点才过

思路

考虑最优路径是什么。
显然，每个点如果需要购买，那么需要购买的物资应该在起始节点到本节点路径中价格最便宜的节点购买（p 值最大）。

换句话说：

假设最优路径路径上第 a_1,a_2,\cdots,a_l 点进行了购买操作。
那么不存在 j \lt a_i，满足 p_j \gt p_{a_i}。

现在我们要考虑什么 dp 状态已经清晰了：

• 目前所在的节点

另外，对于 dp 值，首先需要维护题目要求的最少操作次数，其次，还需要计算到达当前节点剩余的物资。

dp[i][j][k][l] = pair<int,int>

维护个 queue 跑 dp 就搞定了（其实就是 bfs）
复杂度 O(n^4)。

submission