@WSEDWZD
by Xxzxx @ 2018-07-20 12:10:10
$...................$
by WSEDSWZD @ 2018-07-20 12:10:56
@[WSEDSWZD](/space/show?uid=66141)
by Xxzxx @ 2018-07-20 12:11:08
%%%
by Xxzxx @ 2018-07-20 12:11:23
又爆5了……
by Xxzxx @ 2018-07-20 12:18:24
#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 23:02:16
#### 整理一下上面这位的代码：
```
#include<bits/stdc++.h>
#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 2012GFKKKZ @ 2023-08-04 08:31:06