既然老师要求那就写一下题解吧，正好之前今早刚学完与区间dp有关的芝士。

题意描述

在平面上有 n 个点，可以再插入 k 个点。从某个点开始，向右或向下走（要求走到的位均有点），最多可以走多少个点。

有如下明显的性质：

最优解一定会插入 k 个点。

路径中在第一个原有点前面插入点对最优解是没有帮助的，可设最优解一定从原有点开始。

大致思路

我们看到n≤500,很容易想到O(n^3)的做法。然后这题实际上就是一题二维的LIS（最长不下降子序列）。

我们需要先把输入的点进行排序，然后设dp(i,k)是从第i个枚举到第k个。

之后就可以非常简单地列出状态转移方程:dp(i,k)=max(dp(i,k-dis(i,j)+1+dis(i,j),dp(i,k))

OK，上代码

完结撒花