ABC410D XOR Shortest Walk

给定一个有向图，包含 N 个顶点和 M 条边。顶点编号为 1 到 N ，边编号为 1 到 M 。其中第 i 条边是从顶点 A
_i 指向顶点 B_i 的带权有向边，权值为 W_i 。请找出从顶点 1 到顶点 N 的所有可行路径中，路径包含边的权值进行按位 XOR 运算后的最小值。
N,M <= 1000，0 ≤ W_i < 2^10。

解析

暴力dfs在极端情况下可能路径过多TLE，如果多条路径到达顶点u并产生相同的异或值x，每条路径都会继续向下递归，重复探索相同的子问题。考虑特殊的“顶点复用”搜索方式，本质上是一种记忆化搜索，vis[u][x] 记录是否能到达顶点n，异或值为x。总状态数量最大在 (N+M)max⁡Wi(N+M)\max{W_i} 量级，符合要求。
代码：https://vjudge.net/solution/61941108

ABC410E Battles in a Row

初始状态下生命值为 H ，魔法值为 M ，要 依次 击败 N 个怪物，击败第i个怪物消耗生命值为 A_i ，或者消耗魔法值为 B_i 。生命值与魔法值必须大于等于 0。求最多击败的怪物数量。
H,M,N,A_i,B_i <= 3000。

解析

简单DP。定义 dp[i][j] 为击败第 i 个怪物，消耗 j 生命值消耗的最小魔法值。最大的 ans 存在 dp[ans][j]<=m (j<=h) 即为答案。
代码：https://vjudge.net/solution/61943495