[CSP-J 2022] 上升点列

题意

只能向右、向上走，坐标单调不减；最多额外加 $k$ 个点，求最长点序列。
两点 $j$ 到 $i$ 需要插入点数：

$$d=(x_i-x_j)+(y_i-y_j)-1$$

DP

1. 所有点按 $x$ 升、$y$ 升排序
2. 状态：$dp[i][t]$ 以第 $i$ 个点结尾，用了 $t$ 个新增点的最大长度
3. 初始化：$dp[i][0]=1$
4. 转移：$j<i$ 且 $y_j\le y_i$，花费 $d$ 个新增点

$$dp[i][t]=\max(dp[i][t],dp[j][t-d]+d+1) \quad(t\ge d)$$

5. 答案：遍历所有 $dp[i][t]+(k-t)$ 取最大值

Solution

#include<bits/stdc++.h>
using namespace std;
struct P{int x,y;}p[505];
int n,k,dp[505][105],ans;
bool cmp(P a,P b){return a.x==b.x?a.y<b.y:a.x<b.x;}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y,dp[i][0]=1;
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++){
            if(p[j].y>p[i].y)continue;
            int d=p[i].x-p[j].x+p[i].y-p[j].y-1;
            for(int t=d;t<=k;t++)
                dp[i][t]=max(dp[i][t],dp[j][t-d]+d+1);
        }
    for(int i=1;i<=n;i++)
        for(int t=0;t<=k;t++)
            ans=max(ans,dp[i][t]+k-t);
    cout<<ans;
    return 0;
}