关于P1280 尼克的任务的抽象分析
题意抽象模型
一个大区间内有多个小区间，选择一些区间，使得所有区间的 起点 要么被覆盖，要么被选择，且使得没有被覆盖的大区间碎片长度和最大
分析步骤
- 分析两种方法本身逻辑
- 列出两种方法代码上不同点
- 分析不同原因
- 分析共同主要逻辑
- 将主要逻辑思路与自己先前的错误思路比对
- 思考该逻辑延申可以变式成何样
法一：顺序
- 初始化为负无穷
- 按时间顺序遍历
- 将当前点的价值散射给后方的点
- 作为某区间起点，只能散射给对应终点
- 不作为某区间起点，只能散射给后一个点
- 取最后一点后一位作为答案
for(int i = 2; i <= n; ++i) dp[i] = -1e9;//要初始化
for(int i = 1; i <= n; ++i) {//顺序散射
if(!head[i]) dp[i + 1] = max(dp[i + 1], dp[i] + 1);//要取max
for(int j = head[i]; j; j = e[j].next)
dp[e[j].w] = max(dp[i], dp[e[j].w]);
}
printf("%d", dp[n + 1]);//最后一点后一位法二：逆序
- 按时间逆序遍历
- 从当前点收束后方点的价值
- 作为某区间起点，只能由对应终点收束
- 不作为某区间起点，只能由后一个点收束
- 取第一个点作为答案
//不初始化
for(int i = n; i; --i) {//逆序收束
if(!head[i]) dp[i] = dp[i + 1] + 1;//不取max
for(int j = head[i]; j; j = e[j].next)
dp[i] = max(dp[i], dp[e[j].w]);
}
printf("%d", dp[1]);//第一个点共同主要逻辑
- 以区间的点为最小单位，凡是处理一个点时，都是处于任一此点可处理的终状况里 // dp本质
- 所有的散射或是收束，都是以 小区间起点 为中心 // dp 转移方向关键
不同点分析
- 顺序时，将价值从当前点散射到后方，形成一个向后的开口，将后方的部分点包围。遍历到后方的点时，这个点可能就已经处于散射的线条内了，所以本身会受到影响，其价值不一定为真实可达的价值，因此初始化负无穷判断能否为真。
- 逆序时，将价值从后方点收束到当前点，也形成一个向后的开口，不过不会包围后边遍历到的点，也就是前方的点。遍历到前方点时，这个点一定没有被包围，其依旧不受影响，对于目前状态的价值一定为真，其余状态的真假会在以后判断，因此无需初始化。
- 取 max 的问题：收束时，此点一定是第一次处理其价值。散射时，后方的点当被遍历到而处理时，可能已经被先前的散射处理过价值。
- 答案位置问题：收束的点就是答案的点，n + 1 位置的价值遍历的第一点就已经处理。散射的点时答案的点，最后一个散射到的点是 n + 1。
- 对于先前讨论逆序可行顺序不可行的问题，只是因为其转移过程是收束，逆序时才是收束，只要将转移过程改为散射，那就可以顺序处理。
比较该逻辑和自己的错误逻辑
- 可以保证遍历到一个转移中心时，其当前状况是可以判断的。此题中的状况为是否被覆盖，顺序时利用负无穷的初始化来判断，逆序时可以直接判断为当前未被覆盖。
- 我将区间终点作为 dp 转移中心，顺序收束，使得区间起点的状况难以处理，以至于无法解题。
- 提到顺序时可以用负无穷的初始化来判断，其本质是存在一定不确定性，那我们想想以终点为中心导致的不确定性是否可以由此解决。
- 思考得出：后者的不确定性，来源于收束时，因为终点不需要被覆盖，所以需要找所有能够覆盖 以当前点为终点的区间的起点 的区间，取他们转移到此点后的价值的最大值，这个寻找就是最大的不确定。前者是确定了那个点，不确定性只是判断能否转移。因此两者不同。
启发
- 做 dp 时找好转移中心，收束或是散射都依靠它。
- 收束来的方向需要是已遍历过的方向，散射的方向是未遍历过的方向。
- 思考收束来或散射去的点时，他们最好是能确定的。
模型变式
- 求碎片长度和最小值：逆序中改为 min 即可。