\(\color{red}(1)\) P2296 [NOIP2014 提高组] 寻找道路
-
在有向图 \(G\) 中，每条边的长度均为 \(1\)，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
-
路径上的所有点的出边所指向的点都直接或间接与终点连通。
-
在满足条件 \(1\) 的情况下使路径最短。
注意：图 \(G\) 中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。
-
-
\(n \le 10^4\)，\(m \le 2 \times 10^5\)。
显然的想法是，我们将所有满足「所有出边所指向的点都直接或间接与 \(t\) 连通」的点拿出来建图，然后求 \(s\) 到 \(t\) 的最短路即可。问题是如何找到这些点。
首先可以建反图，从 \(t\) 开始 dfs，求出所有能到达 \(t\) 的点并标记。然后枚举每一个点，检查它的出边能否都被标记即可。
\(\color{red}(2)\) P5662 [CSP-J2019] 纪念品
-
小伟突然获得一种超能力，他知道未来 \(T\) 天 \(N\) 种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。
每天，小伟可以进行以下两种交易无限次：
- 任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品；
- 卖出持有的任意一个纪念品，以当日价格换回金币。
每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。当然，一直持有纪念品也是可以的。
\(T\) 天之后，小伟的超能力消失。因此他一定会在第 \(T\) 天卖出所有纪念品换回金币。
小伟现在有 \(M\) 枚金币，他想要在超能力消失后拥有尽可能多的金币。
-
\(T ,N \le 100\)，\(M \le 1000\)。
一个观察，可以发现如果我持有一个物品多天（例如在 \(s\) 天买，\(t\) 天卖），相当于在 \(s + 1 \sim t - 1\) 这些天中，先将这个物品卖掉，再买回。
所以我们不需要记录每天手里持有多少纪念品，统一认为今天买的纪念品，明天就立刻卖掉。
设计 \(dp_{i, j, k}\) 表示第 \(i\) 天，考虑第 \(j\) 个物品，当前手中还有 \(k\) 元时，明天早上能获得的最大收益。则转移：
\[dp_{i, j, k} = \max(dp_{i, j - 1, k}, dp_{i, j - 1, k + p_{i, j}} + p_{i + 1, j}) \]然后我们求出 \(dp_i\) 中的最大值，作为下一天的起始钱数（与 \(m\) 类似）。
标签：24,纪念品,09,金币,le,出边,换回,CSP,dp From： https://www.cnblogs.com/2huk/p/18134124