上升点列 (CSP-J 2022)

因为题目规模很小(n < 500, k < 100)，所以我们考虑三次方复杂度的算法， $\mathcal{O}(n^2k)$ 是可以的：

将所有点按 $x$ 然后 $y$ 的顺序排序，按此顺序进行DP。
$dp[i][j]$ 表示使用前 $i$ 个已有点和 $j$ 个添加点的情况下的最大分值，这样 $ans = max(dp[i][k]), i=1..n$
转移方程是：

$dp[i][j] = \max(dp[a][j-d]+d+1)$ , $a=1..i-1$ 且 $y[i] \geq y[a]$

其中 $d = (x[i]-x[a]) + (y[i]-y[a]) - 1$

最后复杂度是 $\mathcal{O}(n^2k)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n,k;
pi pts[505];
int dp[505][105];
int ans;
 
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d %d", &pts[i].first, &pts[i].second);
    sort(pts+1, pts+n+1);
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= k; j++)
            dp[i][j] = j+1;     // initialize: point i and j added points
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a < i; a++) {
            if (pts[i].second < pts[a].second) continue;
            int d = pts[i].first - pts[a].first + pts[i].second - pts[a].second - 1;
            for (int j = d; j <= k; j++)
                dp[i][j] = max(dp[i][j], dp[a][j-d] + d + 1);
        }
    }
    for (int i = 1; i <= n; i++)
        ans = max(ans, dp[i][k]);
    printf("%d\n", ans);
    return 0;
}