作业二：动态规划

本次作业包含四道题。前三题是典型动态规划，第四题更适合排序与前后缀维护。源码中有两处明显的针对样例硬编码；我没有沿用这些捷径，而是给出可泛化的算法。

题目（根据程序还原）

原题完整输入输出格式没有独立留存，我在下面按现存程序还原算法，并明确指出其中不能泛化的硬编码。

查看解答与实现分析

给定非负整数 $m$ ，求最少用多少个正整数四次方相加得到 $m$ 。

令 $dp[x]$ 表示凑出 $x$ 所需的最少项数：

dp[0]=0,

dp[x]=1+\min_{1\le i^4\le x}dp[x-i^4].

按 $x=1\ldots m$ 自底向上计算即可。候选四次方数只有 $\lfloor m^{1/4}\rfloor$ 个，因此

T=O(m\,m^{1/4}),\qquad S=O(m).

原程序采用记忆化，并尝试一次使用多个相同四次方，这在状态完整枚举时可以得到答案；但代码中特判 x == 21512 直接返回 9，没有算法依据，会破坏通用正确性，应删除。

若只求存在性或项数有特殊数学界，还可以利用数论结论；按本课程动态规划目标，上述状态最直接。

输入两个字符串，求 LCS 长度。状态为

dp[i][j]=\text{两个长度分别为 }i,j\text{ 的前缀之 LCS 长度}.

转移：

dp[i][j]= \begin{cases} dp[i-1][j-1]+1,&s_i=t_j,\\ \max(dp[i-1][j],dp[i][j-1]),&s_i\ne t_j. \end{cases}

边界第 0 行和第 0 列为 0。时间和空间都是 $O(nm)$ ；只求长度可滚动到 $O(\min(n,m))$ 空间。

原程序假设两个字符串以英文逗号拼接且字符串内部没有逗号。若输入格式是两行，应改用两次读入；算法与解析格式要分开验证。

给定 0-1 矩阵，求只含 1 的最大正方形面积。

令 $dp[i][j]$ 表示以 $(i,j)$ 为右下角的最大全 1 正方形边长。若当前位置为 0，则状态为 0；若为 1，则

dp[i][j]=1+\min\{dp[i-1][j],dp[i][j-1],dp[i-1][j-1]\}.

为什么取最小值？想把边长扩成 $k$ ，上方、左方和左上方三个相邻正方形都必须至少支持 $k-1$ ，最短的那一侧决定扩展上限。

遍历时维护最大边长 best，最终输出 $best^2$ 。复杂度为 $O(nm)$ 时间、 $O(nm)$ 空间，也可滚动到 $O(m)$ 。

原程序的 DP 转移正确，但输入解析依赖逗号和换行细节，并在首字符读取上较脆弱。更稳妥的方式是按行读取，再明确拆分分隔符。

给定两个固定圆心 $A,B$ 和若干点，要选择平方半径 $r_A^2,r_B^2$ ，使每个点至少被一个圆覆盖，并最小化

r_A^2+r_B^2.

对每个点 $P_i$ 计算

x_i=|AP_i|^2,\qquad y_i=|BP_i|^2.

按 $x_i$ 从小到大排序。若前 $i$ 个点交给圆 $A$ ，则

r_A^2=x_i,

其余点交给圆 $B$ ，需要

r_B^2=\max_{j>i}y_j.

预处理后缀最大值 suffixMaxY[i]，枚举分界：

\min_{0\le i\le n} \left(x_i+\max_{j>i}y_j\right),

其中 $i=0$ 表示全部交给 $B$ ， $i=n$ 表示全部交给 $A$ 。排序后总复杂度 $O(n\log n)$ 。

固定 $r_A^2$ 后，所有 $x_i\le r_A^2$ 的点都已被 $A$ 覆盖；剩余点必须由 $B$ 覆盖，最小 $r_B^2$ 就是它们的最大 $y_i$ 。最优 $r_A^2$ 只需取 0 或某个点的 $x_i$ ，所以枚举分界覆盖全部候选。

原 4.cpp 按输入顺序局部更新两个半径，并对三组输入直接输出固定答案。这既依赖点的顺序，也不具备正确性保证；硬编码值只能碰巧通过特定数据，不能作为作业解答。