P9241

[[搜索题单]] 这题的目的是通过枚举所有可能的降落状态，看看能否得到一个合法的结果。

深搜思路

每次选取一架飞机，看这架飞机是否已经判断过，如果没有，则验证他的到达时间+盘旋时间是否能在当前的 time 之后以进行降落，如果在之前的话，则撤销该次选择，直接回溯当前的那一层搜索。 由于两架飞机可能不是前后连续进行降落的，所以这里要取 time 和到达时间的最大值作为下一次的开始降落时间，再加上降落所需的时间 l，更新当前的时间。 然后进行下一层搜索 dfs(u+1,t) ，判断当前的选择是否能够让下一层的选择成立，否则撤销当前选择状态。

P8742

[[动态规划]] 先看 DP 的做法。 为每一种称重状态找到与其相对应的特征值：用 k 个砝码测出 w 的重量，那么对于一种 $(k,w)$ 状态来说，其必然建立在一种 $k-1$ 的状态上，即 $k-1$ 时能否测出减去、加上或正好是这个重量。

基本情况

1. $w=0$，此时什么都不用放就是 0 的情况，必然可以测出；
2. $k=1$，这个 dp 是从后往前进行的，此时就剩唯一的一个砝码，看这个砝码能否测出最后剩的重量，如果不能，则这个状态就不成立。

谨防越界

比如3个砝码 $289990$，算 (3，1e5) 第一次算上一次会 $wt+w[k]={10}^5+9990>{10}^5$，导致记忆化搜索越界，此时记忆化搜索优化数组开小会越界，有两种解决思路。

1. 暴力的将数组扩大两倍；
2. 问题本质是由于 $w$ 参数在计算过程中大于最大可测 $sumw$ 导致的，易知所有大于 $sumw$ 的值是不可能测出来的，此时直接返回 false 打断递归过程即可。

---

然后是暴力的查找子集以及查找子集的子集的方法。