书本整理

书本整理

题目描述

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

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

1×2
5×3
2×4
3×1
1
2
3
4

那么Frank将其排列整齐后是：

1×2
2×4
3×1
5×3
1
2
3
4

不整齐度就是2+3+2=72+3+2=7

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

题目分析

这道题可以采用动态规划的思想进行分析。去掉 k 本书也就相当于选出 m = n - k 本书，则题目可以转变为选出 m 本书使得不整齐度最小。

对于最顶层的一本书不会产生差值，所以我们从第二本开始考虑。第二本书有两种摆放方式

• 接在第一本书后边，产生差值，得到两本书的一种情况
• 独自美丽不产生差值，得到一本书的一种情况

后边的书以此类推，分析如下

code

#include

using namespace std;

const int N = 210;

int n, m, k, t;
int f[N][N];
int a[N];

struct node
{
    int h, w;
}q[N];

bool cmp(node a, node b)
{
    if(a.h == b.h) return a.w < b.w;
    return a.h < b.h;
}

int main()
{
    memset(f, 20, sizeof f);
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) cin >> q[i].h >> q[i].w;
    int res = n - k;

    sort(q + 1, q + n + 1, cmp);

    for(int i = 1; i <= n; i ++) f[i][1] = 0;

    for(int i = 2; i <= n; i ++)
        for(int j = 1; j <= i - 1; j ++)
            for(int r = 2; r <= min(i, res); r ++)
                f[i][r] = min(f[i][r], f[j][r - 1] + abs(q[i].w - q[j].w));
        
    int minn = 0x7f7f7f7f;
    for(int i = m; i <= n; i ++) 
        minn = min(minn, f[i][res]);
    cout << minn << "\n";

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44