既然老師要求那就寫一下題解吧，正好之前今早剛學(xué)完與區(qū)間dp有關(guān)的芝士。

題意描述

在平面上有 n 個點(diǎn)，可以再插入 k 個點(diǎn)。從某個點(diǎn)開始，向右或向下走（要求走到的位均有點(diǎn)），最多可以走多少個點(diǎn)。

有如下明顯的性質(zhì)：

最優(yōu)解一定會插入 k 個點(diǎn)。

路徑中在第一個原有點(diǎn)前面插入點(diǎn)對最優(yōu)解是沒有幫助的，可設(shè)最優(yōu)解一定從原有點(diǎn)開始。

大致思路

我們看到n≤500,很容易想到O(n^3)的做法。然后這題實(shí)際上就是一題二維的LIS（最長不下降子序列）。

我們需要先把輸入的點(diǎn)進(jìn)行排序，然后設(shè)dp(i,k)是從第i個枚舉到第k個。

之后就可以非常簡單地列出狀態(tài)轉(zhuǎn)移方程:dp(i,k)=max(dp(i,k-dis(i,j)+1+dis(i,j),dp(i,k))

OK，上代碼

完結(jié)撒花