边界

初始值

我们只对可以到达的状态进行循环赋值。那么在循环开始前初始值可赋为正无穷或负无穷,这样取 max 或 min 后会使不可到达的情况永远不会被考虑。

memset(f,0x3f,sizeof(f));//INF
memset(f,0xc0,sizeof(f));//-INF

不可到达的状态

不进行循环。

不可递推的状态

状态转移方程的循环变量在这个状态下为空集。

确定边界的关键是状态的定义。

最小字典序方案

UVa1599 [NEERC2010] Ideal Path

输入一个无权无向图,每条边有一个编号(不保证不重复),输出 $1\leadsto n$ 最短路中编号序列字典序最小的一条。

不妨先考虑1的单源最短路。这样我们得到一个最短路图DAG。
我们想在这个图上找到到n的最小字典序路径。
朴素的想法是,可以按路径编号安排dfs,找到n即输出路径并终止程序。
但是,问题在于输入不保证路径编号两两不同,因此如果出现两条编号同样小的边时,我们就不能找到一条路径就返回。
由于没有也不能使用vis[]进行标记,因此复杂度不是 $O(V+E)$ 而是阶乘级。
BOOM。

换个方法?
倒着来,从n开始考虑它是从哪些状态转移而来的,每次选择字典序最小的决策。
但是编号不保证不同,因此选择字典序最小的决策这一行为是不确定的。

假如编号保证不同,
这样做也是不对的。因为字典序是从第一个字符开始比大小,如果要贪,必定是第一个数贪最小,这样依次往后贪。而我们倒推决策恰好是从n推到1向决策数列里填数。这样贪是不对的。

如果我们考虑 n 的单源最短路,再从 1 向 n 倒推决策,问题就迎刃而解了。
且慢,再多想一些,n 到 1 的最短路 和 1 到 n 的最短路是一回事,所以我们可以这样搞。
且慢,原题没有保证编号不同,所以无法选出字典序最小的决策。
那我们就从这里分叉,同时考虑这两个决策转移到的状态。
如果某个时刻决策能比出大小了,就可以扔掉大的决策。
如果推到 1 时还没比出大小,说明我们找出了多条字典序最小路径。

这就是bfs。可以用队列实现。

有一种特化的队列实现,在这个情景下很好用,可以省下一些存储量。
使用vector。
一个 vector 代表当前队列中的节点,依次取出扩展,扩展出的新节点加到vector2里。处理完vector后令 vector=vector2 。如果把这些放在一个 for 循环里,就可以知道当前的扩展次数。听上去没有比 queue 优美?也许你应该试一试。

实际上,这道题就是动态规划输出最小字典序。
定义 dis 是 1 的单源最短路。
那么 dis[u] 即为状态,每次的决策是边。

但是我们为什么搞了个 n 的单源最短路?

不妨先考虑所有编号不同的情况。
求出 1 的单源最短路。
从 1 开始搜

NOI1998 免费馅饼

题面略去。要求输出字典序最小方案。