关于判定性问题和最优化问题的联系的一些思考

判定性问题 是指在某些约束条件下，给定命题判断 是否成立 的一系列问题。

比如：给定一张无向图 (G)，判断图是否连通。

答案只可能是两种：连通 和 不连通。这就是一个判定性问题。

最优化问题（optimization problem）的一般提法是要选择一组参数（变量），在满足一系列有关的限制条件（约束）下，使设计指标（目标）达到最优值。

通俗地讲，最优化问题 是指在某些约束条件下，设法找到一组构造方式（解），使得此方式在所有的构造方式中是最优的。

比如：给定一张无向图 (G)，输出最少需要添加多少条边使得图 (G) 连通。

可能的答案有很多种，每一个可能的答案都对应了一组解，即一组待添加的边，但是需要在所有可能的答案中找到一个答案添加的边最少，也就是在此问题下的最优解。这就是一个最优化问题。

假设 ((c, x_0)) 表示一个最优化问题：在约束条件 (c) 下的最优解为 (x_0)，假设 ((c, x, t)) 表示一个判定性问题：在约束条件 (c) 下的解 (x) 是否能够取到，如果可以则 (t = 1)，否则 (t = 0)。

在某些时候，((c, x_0)) 与一系列的 ((c, x, t)) 可以互相转化。

最经典的一个例子就是 二分答案。

例如以下问题：

给定一个元素互不相同序列 (a)，请求出序列中最大的元素。

这是一个简单的 最优化问题，我们可以轻而易举的枚举序列 (a) 中的所有元素，互相比较来解决这个问题，这是一个线性的算法。

出人意料地，这个 最优化问题 可以转化为 判定性问题：

给定一个元素互不相同序列 (a)，请判断 (x) 是否是序列中最大的元素。

我们可以讲序列中所有 (< x) 的数都置为 (0)，序列中所有 (ge x) 的数都置为 (1)，这样只需要判断序列中元素的和是否为 (1) 即可判断。

而沟通这个 最优化问题 和 判定性问题 的桥梁就是 二分答案，如果枚举每一个 (x) 即可转化为上述 判定性问题，这个过程可以通过 二分答案 优化。

如果 (n) 是数组长度，时间复杂度是 (O(nlog n)) 的，这个二分答案的算法可以扩展到区间多次第 (k) 大数，也就是著名的 整体二分 算法。

在这个简单的例子中似乎体现不了 转化 的必要性，但在以下这道题目中这种转化是十分必要的。

给定的一个长度为 (N) 的正整数数列 (A_{1sim N})，现要将其分成 (M)（(Mleq N)）段，并要求每段连续，且每段和的最大值最小。

通过二分答案的 转化，将问题转化为如下判定性问题：

给定的一个长度为 (N) 的正整数数列 (A_{1sim N})，每一段的最大值不得超过 (x)，能否将序列分成不超过 (M) 段。

此判定性问题可以贪心求解。

沙漠中有 (n) 个绿洲（编号为 (1-n) ）和 (e) 条连接绿洲的双向道路。每条道路都有一个长度 (d) 和一个温度值 (r) 。给定起点绿洲编号 (s) 和终点绿洲编号 (t) ，求出一条 (s) 到 (t) 的路径，使得这条路径上经过的所有道路的最高温度尽量小，如果有多条路径，选择总长度最短的那一条。

通过二分答案的 转化，将问题转化为判定性问题，解法略。

有一座高 (n) 层的楼，你拥有 (m) 个相同的水球，一个水球从承受程度以下的楼层丢下不会破裂，否则会破裂，一旦破裂你会失去这个水球。

请问最少多少丢多少次水球可以将水球的承受限度测出来，如果次数多于 (63) 次则输出 "More than 63 trials"，(nle 2^{64} - 1, m le 100)。

这是一个经典的动态规划问题，其原本的状态表示为 (dp[i][j]) 表示 (i) 层楼，用 (j) 个水球，最少多少次测出水球承受程度。

但是在这道题中完全无法存储这么大的状态，所以考虑优化状态表示。

通过 转化，(dp[i][j][k]) 表示 (i) 层楼，用 (j) 个水球，能否在 (k) 步内测出。

通过 转化，(dp[i][j]) 表示 (i) 个水球，(j) 步内最多测到多少层楼水球的承受程度，此状态表示可以实现转移。

最后枚举步数，比较 (n) 与 (dp[m][i])，即可得出 (j) 步内是否能够测到 (n) 层楼的承受程度。

在这道题中通过将 最优化问题 转化为 判定性问题，又将 判定性问题 转化为另一个 最优化问题 之后使用动态规划算法求解。

给定 (N) 个立方体箱子，其中第 (i) 个箱子的高为 (h_i)，宽为 (w_i)，深为 (d_i)。

箱子可以任意翻转、旋转。请判定是否存在一对箱子，使得一个箱子可以严格容纳下另一个箱子。也就是说，把箱子 (j) 装到箱子 (i) 里面之后，（翻转/旋转）后对应的高、宽、深满足 (h_igt h_j)，(w_igt w_j)，(d_igt d_j)（请注意是严格大于）。

若存在，输出 Yes；否则输出 No。

由于可以旋转，所以首先对 (h, w, d) 排序，假设 (h_i le w_ile d_i)，问题转化为是否存在一个三维偏序关系，对于偏序问题，可以套路地将箱子按 (h) 排序，转化为是否存在 (i < j, w_i < w_j, d_i < d_j)，用数据结构维护 (w) 这一维，剩下可以使用 CDQ 分治做，不过有更好的解法。

由于这是一个 判定性问题，可以考虑转化为 最优化问题：

则原问题等价于判断是否

只需要用一棵下标为 (w_i)，元素为 (d_i) 的线段树即可解决这个单点修改，区间查询最小值问题。

信息学中有很多类似的问题转化，如果在某些 判定性问题 或者 最优化问题 中思路陷入了僵局，不妨考虑 转化 为另一个容易解决的问题。

由于作者水平有限，文中的错误在所难免，希望读者批评指正。