#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define maxn 105
using namespace std;
int n,k;
struct Book{int h,w;}a[maxn];
int f[maxn][maxn];
int abs(int x){return x<0?-x:x;}
int dfs(int now,int cnt,int xuan){
if(f[now][cnt]!=-1) return f[now][cnt];
int ans=19260817;
if(now==n) return 0;
if(n-xuan==k) return 0;
if(cnt==k) return f[now][cnt]=dfs(now+1,cnt,xuan+1)+abs(a[now+1].w-a[now].w);
for(int i=1;i<=n;i++)
if(now+i<=n&&cnt+(i-1)<=k) ans=min(ans,dfs(now+i,cnt+(i-1),xuan+1)+abs(a[now+i].w-a[now].w));
return f[now][cnt]=ans;
}
bool cmp(Book aaa,Book bbb){return aaa.h<bbb.h;}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].h,&a[i].w);
sort(a+1,a+n+1,cmp);
memset(f,-1,sizeof(f));
int ans=19260817;
for(int i=1;i<=k+1;i++){
ans=min(ans,dfs(i,i-1,1));
}
printf("%d",ans);
return 0;
}
by zhouzhengye @ 2019-06-05 22:54:44
给你一个帖子
慢慢抄吧
大佬程序100%无敌
by zhouzhengye @ 2019-06-05 22:57:07
巧了我居然也在3和7wa了
by return_TLE @ 2023-01-24 10:16:57