洛谷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 \leq n \leq 100, 1 \leq k < n$ )

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

保证高度不重复

输出格式

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

输入输出样例

输入：输出：

4 1 3

1 2

2 4

3 1

思路：

首先这很明显是一道dp，状态之间的转移很好想，所以我很快就想出了状态转移方程：对于第i本书，我们可以选择拿走或者不拿走（留下这本书），如果拿走这本书的话那么不整齐度不会有任何变化。如果留下这本书的话，那么不整齐度就要加上留下的这本书的不整齐度和留下这本书之前底部的书的不整齐度的差的绝对值。我用数组f[i][j]记录前i本书拿走了j本书之后的最小不整齐度，然后写出状态转移方程，却连样例都没过。后来我发现好像是无法正确循环在留下这本书之前底部的书的编号，而且我想了半天也无法想出怎么循环上一个状态的底部书籍编号。在沉浸在被黄题乱杀的痛苦之中的同时，我无奈地查看了题解。我觉得题解的思路很巧妙，一共有n本书，拿走了m本书，那也就是剩下了n-m本书，将问题转化为了类似的dp题目。而且我的二维数组表示的信息也有问题，因为它不能准确地定位在留下这本书之前最底部的书籍的编号是多少。

题解中f[i][j]表示以第i本书为最底部的书籍时留下j本书的最小不整齐度。那么这个时候只需要多加一层循环就能够很好地记录上一个状态中最底部书籍的编号了，这样我们就可以切掉这道题目了。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
int n,m,l;
int f[110][110];//换另一种思路，f[i][j]表示以第i本书结尾，共留下了j本书 
struct shu{
    int gao,kuan;
}a[110];
int cmp(shu x,shu y){
    return x.gao<y.gao;
}
int main()
{
    scanf("%d%d",&n,&l);
    m=n-l;//留下m本书 
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].gao,&a[i].kuan);
    } 
    sort(a+1,a+1+n,cmp);
//    for(int i=1;i<=n;i++){
//        printf("%d %d
",a[i].gao,a[i].kuan);
//    }
    memset(f,0x3f,sizeof(f));
    //初始化
    f[0][0]=0,f[1][1]=0,f[1][0]=0,f[1][0]=0;
    for(int i=2;i<=n;i++){
        f[i][i]=f[i-1][i-1]+abs(a[i].kuan-a[i-1].kuan);//若全部留下的话 
        f[i][1]=0;
        f[i][0]=0;//留下0本书和1本书都是0不整齐度 
    }
//    for(int i=1;i<=n;i++){
//        printf("%d ",f[i][i]);
//    }
//    printf("
");
    for(int i=2;i<=n;i++){
        for(int k=1;k<i;k++){//循环放这本书之前最底层的书 
             for(int j=2;j<=min(i,m);j++){//循环当前已有书的个数，循环顺序交换也可以，只要保证最外层循环不变即可 
                f[i][j]=min(f[i][j],f[k][j-1]+abs(a[i].kuan-a[k].kuan));//以第i本书为最底部书籍时有j本书的最小不整齐度，要从以第k本书为最底部书籍时有j-1本书的最小不整齐度加上第i本书和第k本书差的绝对值 
            }
        }
    }
    int minn=1000000000;
    for(int i=m;i<=n;i++){
        minn=min(minn,f[i][m]);//最底层的书的编号最小也是m，因为要留下m本书，而最底层书最大编号当然是最后一本，因为可以不拿它 
    }
    printf("%d
",minn);
    return 0;
}