[CSP-J 2022] 上升点列
题意
只能向右、向上走，坐标单调不减；最多额外加 kkk 个点，求最长点序列。
两点 jjj 到 iii 需要插入点数：
d=(xi−xj)+(yi−yj)−1d=(x_i-x_j)+(y_i-y_j)-1 d=(xi −xj )+(yi −yj )−1
DP
1. 所有点按 xxx 升、yyy 升排序
2. 状态：dp[i][t]dp[i][t]dp[i][t] 以第 iii 个点结尾，用了 ttt 个新增点的最大长度
3. 初始化：dp[i][0]=1dp[i][0]=1dp[i][0]=1
4. 转移：j<ij<ij<i 且 yj≤yiy_j\le y_iyj ≤yi ，花费 *** 个新增点
dp[i][t]=max(dp[i][t],dp[j][t−d]+d+1)(t≥d)dp[i][t]=\max(dp[i][t],dp[j][t-d]+d+1) \quad(t\ge d) dp[i][t]=max(dp[i][t],dp[j][t−d]+d+1)(t≥d)
5. 答案：遍历所有 dp[i][t]+(k−t)dp[i][t]+(k-t)dp[i][t]+(k−t) 取最大值
SOLUTION
