目录一、LIS 优化二、LCS 优化全排列三、LCIS 优化四、逆向线性DP优化五、上升点列六、守望者的逃离七、尼克的任务八、饥饿的奶牛九、最长前缀一、LIS 优化优化技巧low[len]存长度为len的上升子序列最小末尾严格单调递增。x low[top]追加否则二分替换。严格上升用lower_bound不下降用upper_bound。时间复杂度O ( n 2 ) O(n^2)O(n2)-----O ( n l o g n ) O(n log_n)O(nlogn​)。评价注意查找的边界加强版卡了我好久。二、LCS 优化全排列优化技巧两序列均为1 ~ n全排列时pos[a[i]]i将b映射为c[j]pos[b[j]]求c的 LIS。时间复杂度O ( n 2 ) O(n^2)O(n2)-----O ( n l o g n ) O(n log_n)O(nlogn​)。评价比较特殊一般是模版。三、LCIS 优化优化技巧固定外层 i 扫描 j 时维护val满足b[k]a[i]的dp[i-1][k]最大值A[i]B[j]时直接赋值吃掉最内层k循环。时间复杂度O ( n m 2 ) O(n m^2)O(nm2)-----O ( n m ) O(n m)O(nm)。评价我无话可说。四、逆向线性DP优化优化技巧正向需记录“剩余忙碌时间”导致维度爆炸逆向定义dp[t]为从t tt到终点的最优值倒序扫描。评价zl 又以一种奇奇怪怪的方式进了机房。T1~T3解决方式如上不做讲解。五、上升点列问题n nn个整点最多添加k kk个求最长上升点列总数量。思路按x xx升序、x xx同按y yy升序排序。dp[i][p]以第 i 点为末尾、消耗 p 个添加点。评价几乎是一道板子LIS。六、守望者的逃离问题距出口S SS米T TT秒内逃脱每秒可选瞬移、回复魔法或跑步。思路跑两次。第一轮闪烁/回蓝第二轮跑步修正dp[t]max(dp[t],dp[t-1]17)每秒检查到达。评价影分身不是很难。七、尼克的任务问题n 分钟内 k 个任务某时刻有任务必须选一个无任务可休息求最多休息时间。思路逆向dp[t]为从 t 到 n 的最长休息时间。倒序无任务dp[t]dp[t1]1有任务dp[t]max(dp[tlen])。评价逆向DP板子。八、饥饿的奶牛问题n nn个区间选不相交区间使总长度最大坐标范围3 × 10 6 3 × 10^63×106。思路dp[i]为[ 0 , i ] [0,i][0,i]内最大总长度。初始化dp[i]dp[i-1]i ii不作为右端点对每个以i ii为右端点的区间[ x , i ] [x,i][x,i]若x 0 x0x0则dp[i]max(dp[i],dp[x-1]i-x1)若x 0 x0x0则dp[i]max(dp[i],i-x1)不可继承遗产直接取本段。评价注意边界否则你会RE/WA到怀疑晗源。九、最长前缀问题短字符串集合P长度≤ 10 ≤ 10≤10和母串 S长度≤ 2 × 10 5 ≤2 × 10^5≤2×105求能拼出的最长前缀长度。思路vis[i]布尔表示S SS前i ii字符能否由P PP中元素拼出。初始化vis[0]1。对每个位置i ii枚举P PP中每个单词若长度不超过i ii且vis[i-len]true且S.substr(i-len,len)等于该单词则vis[i]true并break。用ans记录最大的可达i ii。评价布尔可达性DP单词长度上限小是突破口。