P10377 [GESP202403 六级] 好斗的牛 题解

题意

有大量牛棚，安排n头牛。第i头牛左边a_i个牛棚、右边b_i个牛棚不能出现别的牛。
要选出一段连续牛棚，把全部n头牛放进去，满足互不冲突。求这段连续牛棚的最小总数量。
n <= 9。

思路

1. n最多为9，可以暴力枚举所有牛的摆放先后顺序（全排列，参考 P1706 全排列问题）。
2. 确定摆放顺序之后，只计算相对位置：第一头牛放在相对位置0。
3. 相邻两头牛，前牛是pre，后牛是cur。两者之间最小间隔：max(b[pre], a[cur]) + 1。
   前一头向右攻击b[pre]，后一头向左攻击a[cur]，两者必须躲开对方攻击范围。
4. 顺着排列累加相对位置，算出该排列需要的连续牛棚总长度。
5. 在全部排列结果里取最小值，就是答案。

核心原理：
牛的实际绝对位置不重要，只关心互相之间的相对距离；n=9，全排列9! = 362880，计算量完全可以接受。

样例1：
n=2，a=[1,2]，b=[1,2]
两种排列：
顺序0，1：间隔 max(b[0],a[1])+1 = max(1,2)+1 =3；总长度 0+3+1 =4
顺序1，0：间隔 max(b[1],a[0])+1 = max(2,1)+1 =3；总长度也是4。
最小值4，和样例输出一致。

实现要点：
DFS回溯生成全排列；calc函数根据排列算出需要牛棚数；维护全局最小值。

P10376 [GESP202403 六级] 游戏 题解

题意

给定n,a,b,c。每轮可以选择 n减去a 或者 n减去b。当n <= c游戏结束。求不同操作序列的数量。
即使a等于b，两种减法算作不同操作。答案对 10^9+7取模。
n <= 2*10^5。

思路：记忆化搜索 / DP

• 简单考虑的话不做记忆化，纯粹暴力DFS(num-a), DFS(num-b)，在num < C时 ans++，也能得部分分数。
• dp[now]代表当前数值为now的时候，一共有多少种合法操作序列。
• 边界条件：now <= c，游戏直接结束，这是1种方案。
• 状态转移：当前大于c，可以选减a，或者选减b，所以now的序列总量就是now-a和now-b序列量之和，有点像爬楼梯（斐波那契）问题。
  dp[now] = (dp[now‑a] + dp[now‑b]) % MOD
• 使用记忆化递归，或者迭代DP从c+1推到n。

核心原理：
每一步两种选择，子问题独立；已经算过的状态保存结果避免重复计算。
当now已经小于等于c，不再进行操作，代表一条完整操作序列完成，贡献方案数1。

样例1：
输入 1 1 1 1
now=1，满足now<=c，直接返回1，输出1。

实现要点：
递归记忆化注意数组大小；每一步取模；也可以写成循环DP。

P11246 [GESP202409 六级] 小杨和整数拆分 题解

题意

把n拆成若干完全平方数相加，要求使用平方数的个数尽可能少，输出最小数量。
n <= 10^5。

思路：DFS剪枝搜索

• 暴力DFS，每次从n里减去一个完全平方数，剩下的数扔进DFS继续处理，直到变成0
• 搜索参数：剩余数值n，last限制本次最大可以选用的平方根，ans已经选了多少个平方数。
• 为了不生成重复组合（顺序不同算同一种拆分），强制后面选的平方数不能比上一次的大，i从min(sqrt(n),last)向下枚举。
• 递归边界：剩余n等于0，更新全局最小答案。
• 剪枝：如果当前ans已经大于等于当前最优ans1，直接return，不再继续往下搜。
• 每次选i*i，递归剩下 n‑i*i，上界变成i，计数+1。

核心原理：
题目只关心选哪些平方数，调换顺序不产生新方案，用last限制避免重复搜索；依靠最优解剪枝大幅减少搜索分支。

样例1：
输入18，最优 9+9，两个平方数，输出2。

实现要点：
向下枚举i配合last去重；一定要写最优解剪枝，否则n=1e5会超时。