题解 P1103 【书本整理】

火箭升空 · 2019-12-25 18:29:23 · 题解

首先理解题意：他说要从n本书中去掉k本，也就是说要留下n-k本书

于是我们定义数组f[i][j], 它表示的是前i本中，留下j本，其中一定包括第i本，的最小不整齐度

接下来就该思考如何设状态转移方程了：

因为前i本中要留下j本，第i本又必须留下，所以就相当于前i-1本书留下j-1本，假设j-1到i中留下的书为t，就可以得出：

f[i][j] = min(f[i][j], f[t][j - 1] + abs(a[i].w - a[t].w));(这很好理解，仔细想一下）

下面看具体的代码实现：

#include <bits/stdc++.h>
using namespace std;
#define MAXN 110
struct Edge{
    int h, w;
} a[MAXN];
int sum[MAXN], f[MAXN][MAXN];//表示前i本中，留下j本，其中一定包括第i本，的最小不整齐度 
int n, k;
bool cmp(Edge x, Edge y) {
    return x.h < y.h;
}
int main() {
    cin >> n >> k;
    k = n - k;//直接把k变成要留下的本数
    for (int i = 1; i <= n; i++) {
        cin >> a[i].h >> a[i].w;
    }
    sort(a + 1, a + 1 + n, cmp);
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; i++) {
        f[i][1] = 0;//留下1本， 不整齐度一定是0啦
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= k && j <= i; j++) {
            for (int t = j - 1; t < i; t++) {
                f[i][j] = min(f[i][j], f[t][j - 1] + abs(a[i].w - a[t].w));
            }
        }
    }
    int ans = 0x3f3f3f3f;
    for (int i = k; i <= n; i++) {
        ans = min(ans, f[i][k]);
    }
    cout << ans << endl;
    return 0;
}

这是本蒟蒻第一次发题解，求求管理员给通过啦qwq