P1103 书本整理

题目描述

Frank是一个非常喜爱整洁的人。他有一大堆书和一个书架，想要把书放在书架上。书架可以放下所有的书，所以Frank首先将书按高度顺序排列在书架上。但是Frank发现，由于很多书的宽度不同，所以书看起来还是非常不整齐。于是他决定从中拿掉k本书，使得书架可以看起来整齐一点。

书架的不整齐度是这样定义的：每两本书宽度的差的绝对值的和。例如有4本书：

\(1 \times 2\)
\(5 \times 3\)
\(2 \times 4\)
\(3 \times 1\)
那么Frank将其排列整齐后是：

\(1 \times 2\)
\(2 \times 4\)
\(3 \times 1\)
\(5 \times 3\)
不整齐度就是\(2+3+2=7\)

已知每本书的高度都不一样，请你求出去掉k本书后的最小的不整齐度。

输入格式

第一行两个数字\(n\)和\(k\)，代表书有几本，从中去掉几本。(\(1 \le n \le 100, 1 \le k<n\))

下面的\(n\)行，每行两个数字表示一本书的高度和宽度，均小于\(200\)。

保证高度不重复

输出格式

一行一个整数，表示书架的最小不整齐度。

样例 #1

样例输入 #1

4 1
1 2
2 4
3 1
5 3

样例输出 #1

3

作为开学第一题，感觉自己菜的要死，本来就菜，许久没刷题更菜了/kk

题目解析

其实是一道很容易看出来的DP，然后我非常sb的坚信可以用贪心解决，只要加一些小小的优化

然后在听取wa声一片后才发现是个DP

然后这个思路其实有点巧妙的，我们可以把拿走k本书看作在里面放入n-k本书

我们这里f[i][j]表示前i本书里面拿走j本且第i本必须拿走时的最小不整齐度

看到这里n<=100,然后我们可以很开心地用O（n^3）的时间复杂度跑完

再注意一些细节即可

代码如下

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=105;
struct Node{
  int h,w,_front,_next;
}s[N];
int f[N][N];
int m[N],v[N];
bool cmp(Node x,Node y){
  return x.h<y.h;
}
int main(){
  int n,k;
  scanf("%d%d",&n,&k);
  for(int i=1;i<=n;i++)
    scanf("%d%d",&s[i].h,&s[i].w);
  sort(s+1,s+1+n,cmp);
  memset(f,0x3f,sizeof(f));
  for(int i=1;i<=n;i++){
    f[i][1]=0;
    for(int j=2;j<=min(n-k,i);j++){
      //f[i][j]=0x3f3f3f3f;
      //cout<<f[i][j]<<' ';
      for(int t=1;t<i;t++){
        f[i][j]=min(f[i][j],f[t][j-1]+abs(s[t].w-s[i].w));
      }
      //cout<<f[i][j]<<endl;
    }
  }
  //printf("%d\n",n-k);
  int ans=0x3f3f3f3f;
  for(int i=1;i<=n;i++)ans=min(ans,f[i][n-k]);//,printf("%d\n",f[i][n-k]);
  printf("%d\n",ans);
  return 0;
}