P4913 上升点列（提高）

解题思路

第一步，理解题意。 平面上有n个整数点，我们还可以另外添加k个整数点。添加完以后，要从这些点里选出一列点排成一个序列，要求任意相邻两个点的距离恰好是1，并且横坐标、纵坐标都单调不减（也就是每一步只能向右走一格或向上走一格）。问能排出的序列最长有多长。

第二步，排序简化问题。 因为序列每一步只能向右或向上走，所以序列里的点按横坐标从小到大（横坐标相同时按纵坐标从小到大）排列，正好就是序列的顺序。我们先把所有给定点排序。

第三步，设计DP状态。 定义dp[i][j]表示：以第i个给定点为序列的最后一个点，并且已经用了j个添加点的时候，序列的最大长度。初始时，序列只有第i个点自己，长度是1，即dp[i][0]=1。

第四步，写出转移。 从第t个点走到第i个点，需要先向右走(x[i]-x[t])步，再向上走(y[i]-y[t])步，两点之间的中间点一共有need=(x[i]-x[t])+(y[i]-y[t])-1个。如果x[t]>x[i]或者y[t]>y[i]，就不能从t走到i；如果need大于k也跳过。转移时，从状态dp[t][j-need]加上这need个中间点和第i个点，序列长度增加need+1，即dp[i][j]取max(dp[t][j-need]+need+1)。

第五步，统计答案。 答案就是所有dp[i][j]中的最大值。因为j不能超过k，所以内层循环j从need到k。坐标可能很大，need用long long计算防止溢出。样例n=8、k=2时，最长序列是8，与样例输出一致。

参考代码

// 上升点列：排序后DP，dp[i][j]表示以第i个点为序列最后一个给定点、用了j个添加点时的最长长度
#include <iostream>
#include <algorithm>
using namespace std;
struct Pt { long long x, y; };
Pt p[505];
int dp[505][105];
bool cmp(const Pt& a, const Pt& b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}
int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;
    sort(p, p + n, cmp);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        dp[i][0] = 1; // 序列只有一个点，不需要添加点
        if (dp[i][0] > ans) ans = dp[i][0];
        for (int t = 0; t < i; t++) {
            // 只有t在i的左下角才能从t走到i
            if (p[t].x > p[i].x || p[t].y > p[i].y) continue;
            long long need = (p[i].x - p[t].x) + (p[i].y - p[t].y) - 1;
            if (need < 0 || need > k) continue;
            int nd = (int)need;
            // 从t到i之间要补need个点，整体长度增加need+1
            for (int j = nd; j <= k; j++) {
                if (dp[t][j - nd] > 0) {
                    int v = dp[t][j - nd] + nd + 1;
                    if (v > dp[i][j]) {
                        dp[i][j] = v;
                        if (v > ans) ans = v;
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

排序需要O(n log n)。DP部分有两层枚举点t和i，共O(n²)种配对，每个配对又要枚举j从0到k，所以总时间复杂度O(n²·k)。n最大500，k最大100，500×500×100约2500万，可以轻松通过。dp数组大小n×(k+1)，空间复杂度O(n·k)。