题解 P1103 【书本整理】

· · 题解

先理解题意

对于给出的书本，Frank会先把它们按照高度排好序，接下来通过删去一些书本来达到宽度最整齐；不论怎么删去，都是在原有顺序的基础上抽走。

为我这种DP初学者的详细分析

（以下的“差”指的是差的绝对值）

“抽走”对于整齐度的影响是很奇怪的：减去自己与两旁书本宽度的差，再加上那两书本宽度的差。尽量转化为已学的模型：从 n 本书里面挑出 n-k 本，按原顺序排列达到宽度最整齐。

这是不是很熟悉？如果不，我们一本本地尝试加入，那么“当前试着把哪一本加入”就是状态的一个维度（至少要用 f[i]）。一步步推导出状态转移方程。

取第一本，不用花费（花费即增加“不整齐度”）。

第二本书，

①：假如自顾自，成为一长串书本的队首（也就是忽略第一本，从第二本开始取），不用花费。

②：可是如果接上第一本，要花费，好处是队列长度增加到 2 了。发现了吗？队列长度也是某个维度(至少要用 f[i][l])。

到第三本书，

①：如果忽略前两本，不用花费，但是只取了这么一本书。f[3][1] = 0。

②：如果从第一本或第二本接上，长度都会变成2，那么我们选择花费小的一种方式。f[3][2] = min( f[1][1] + abs (a[3].w - a[1].w), f[2][1] + abs(a[3].w - a[2].w) )。

③：如果前两本都接上，队列成为 1,2,3。

尝试加入第四本书，

①：也可以从自己开始取，f[4][1] = 0。

②：也可以从 1 或 2 或 3 其中一本接上，长度都会变成 2，择优。

③：也可以从长度为 2 的队列接上^，择优。

④：也可以接上 1,2,3 这个长度为 3 的队列。

^此时前三本中花费最小、长度为2的队列已经存储在 f[2][2] 和 f[3][2]，为什么不直接用一个 f[2] 存储？因为第四本与 2,3 两本书相邻的代价是不同的。不存在 f[1][2]，因为取到第一本的时候没有长度为 2 的队列。

第五本，第六本依此类推。

#include<bits/stdc++.h>
using namespace std;

int n, k, m, Min = 0x7fffffff;
int f[501][501];
//f[i][l]：以i作末尾，选了l本书时的最小花费

struct info
{
    int h, w;
}a[1001];

bool cmp(const info & x, const info & y)
{
    return x.h < y.h;
}

int main()
{
    cin >> n >> k;
    m = n - k;//选取m本书 
    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, 20, sizeof(f));//初始极大，能缩小就缩小

    for(int i = 1; i <= n; i++)
        f[i][1] = 0;
    //单独选择任何书都不会有花费

    for(int i = 2; i <= n; i++)//试着放第i本的时候 
        for(int j = 1; j <= i-1; j++)//尝试与前面第j本相邻
            for(int l = 2; l <= min(i, m); l++)//放下第i本时，能从之前长1的队列继承为长2的队列，也能从之前长2的队列继承为长3的队列……l表示放下后的长度
            //显然试到第i本时，长度不会超过i，也不会超过m，m是最终需要的长度

                f[i][l] = min(f[i][l], f[j][l-1] + abs(a[i].w - a[j].w/*这是尝试相邻的书本*/));//放第i本继承到长度为l，总花费越小越好

    for(int i = m; i <= n; i++)
        Min = min(Min, f[i][m]);//i的循环的意思是：以m结尾的队列，可能最小，以m+1结尾的队列也可能的……以n结尾的队列也可能。

    printf("%d\n", Min);
    return 0;
}