线性DP
思路
见:https://www.luogu.com.cn/blog/lwz2002/shu-ben-zheng-li
代码
#include<bits/stdc++.h>
using namespace std;
int n,k;
typedef pair<int,int> PII;
const int N=1e2+10;
PII a[N];
int b[N],f[N][N];
int main()
{
cin>>n>>k;
int m=n-k;
for(int i=1;i<=n;i++)
cin>>a[i].first>>a[i].second;
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
b[i]=a[i].second;
for(int i=2;i<=n;i++)
for(int j=2;j<=min(i,m);j++)
{
f[i][j]=INT_MAX;
for(int q=j-1;q<i;q++)
f[i][j]=min(f[q][j-1]+abs(b[i]-b[q]),f[i][j]);
}
int res=INT_MAX;
for(int i=m;i<=n;i++)
res=min(f[i][m],res);
cout<<res<<endl;
return 0;
}