1. 题目

传送门＝￣ω￣＝

2. 题解

设 $f(i,j)$表示在前 $i$本书中选 $j$本书，且必然选择第 $i$本书时的最小差异值。
不难得出状态转移方程：$f(i,j)=min\{f(k,j-1)+abs(w[k]-w[i]) | j-1<=k<i\}$

因此记忆化搜索就AC了。
递归边界：
1. $i==1$或者 $j==1$时，$f(i,j)=0$
2. $i==j$直接 for 一遍暴力计算差异值。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n,k,f[105][105],ans=INT_MAX;
bool book[105][105];
pii obj[105];
int dfs(int x,int y)
{
    if(book[x][y])return f[x][y];
    book[x][y]=1;
    if(x==1||y==1)return 0;
    if(x==y)
    {
        for(int i=2;i<=x;i++)f[x][y]+=abs(obj[i].second-obj[i-1].second);
        return f[x][y];
    }
    f[x][y]=INT_MAX;
    for(int i=y-1;i<x;i++)
        f[x][y]=min(f[x][y],dfs(i,y-1)+abs(obj[x].second-obj[i].second));
    return f[x][y];
}
int main()
{
    scanf("%d%d",&n,&k),k=n-k;
    for(int i=1;i<=n;i++)scanf("%d%d",&obj[i].first,&obj[i].second);
    sort(obj+1,obj+1+n);
    for(int i=k;i<=n;i++)ans=min(ans,dfs(i,k));
    printf("%d\n",ans);
    return 0;
}