第 377 场力扣周赛

移除栅栏得到的正方形田地的最大面积

题目

输入整数 \(m\) 和 \(n\)，表示宽为 \(m\) 长为 \(n\) 的矩形，左上角为 \((1,1)\)，右下角为 \((m,n)\)。输入长度分别为 \(p\) 和 \(q\) 的数组 \(a\) 和 \(b\)，数组 \(a\) 中的数对矩形水平分割，数组 \(b\) 中的数对矩形垂直分割。输出从数组 \(a\) 和 \(b\) 中移除任意个数，所能够形成的最大正方形面积，结果对 \(10^{9}+7\) 取余。

数据范围：\(3\leq m,n\leq 10^{9}\)，\(1\leq p,q\leq 600\)，\(1<a_{i}<m\)，\(1<b_{i}<n\)。

思路

首先考虑对于宽来说，能够表示的长度是多少。显然，可以通过二重循环枚举出所有可能的长度。将宽能够表示的长度放入哈希表，然后同样使用二重循环枚举长能够表示的长度（假设当前枚举到长度 \(x\)），如果该长度在哈希表中，则说明可以形成长度为 \(x\) 的正方形。最后输出最大值即可。

转换字符串的最小成本 II

题目

输入长度为 \(n\) 的字符串 \(source\) 和 \(target\)，以及长度为 \(m\) 的字符串数组 \(original\)、\(changed\) 和 \(cost\)。其中 \(cost[i]\) 表示将字符串 \(original[i]\) 替换为 \(changed[i]\) 的成本。输出将 \(source\) 转换为 \(target\) 所需的最小成本，如果无法转换则输出 \(-1\)。任意两个替换操作所替换的区间要么相同，要么不相交。

数据范围：\(1\leq n\leq 1000\)，\(1\leq m\leq 100\)，\(1\leq \operatorname{len}(original[i])=\operatorname{len}(changed[i])\leq n\)。

思路

首先使用哈希表将 \(original\) 和 \(changed\) 数组中的字符串映射为数字，每个数字都作为图中的一个顶点。对于每个下标 \(i\)，建立一条从顶点 \(original[i]\) 到顶点 \(changed[i]\) 的边，然后使用 Floyd 算法求出多源最短路径。最后使用动态规划，定义 \(dp[i+1]\) 为对 \(source\) 的前缀 \([0,i]\) 做替换使其和 \(target\) 的前缀 \([0,i]\) 相等，所需的最小代价。注意，外层循环枚举前缀的右端点 \(i\)，内层循环枚举 \(original\) 数组，总时间复杂度为 \(O(m^{3}+n^{2}m)\)。使用字典树会更快，参考灵神题解。