题目内容

P1103

大意:n 本书,各有宽度和高度,现从中抽出 k 本,定义不整齐度为按照高度排好序后相邻两本书的宽度的差值的绝对值之和。求最小不整齐度。

解题思路

首先想了很久,发现考虑“取出”书本的操作不方便实施,但是如果看成“选出其中的 n-k 本”的话,问题就很好想了。

首先考虑状态的设计,由于当前选出结尾的书是有后效性的,对后面加进来的书是有影响的,因此可以打定状态的第一维是:以第 i 本书结尾。然后由于前面选了多少本书也有后效性,并且满足最优子结构,所以定义状态的第二维是选了 j 本,由此得出完整的状态定义:f_{i,j} 表示第 i 本书结尾,选了 j 本(包括第 i 本)在内能达到的最小不整齐度。

至于状态的转移,首先起到作用的肯定是上一本书是什么,因此要循环枚举一层上一本书,然后之前选了多少本也是很重要的,所以这里也要枚举,不难得出方程式:

f_{i,j}=\min\lbrace f_{k,j-1}+|w_k-w_i| \rbrace\quad(k\in[1,i))

时间复杂度 O(n^3),代码如下:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int n,k,f[105][105];

struct book
{
    int w,h;
}a[205];

inline bool cmp(book a,book b)
{
    return a.h<b.h;
}

inline int abs(int x)
{
    return x>=0?x:-x;
}

int main()
{
    memset(f,0x3f,sizeof(f));
    scanf("%d %d",&n,&k);
    int m=n-k;//一共取(n-k)本书
    for(int i=1;i<=n;i++)
        scanf("%d %d",&a[i].h,&a[i].w),f[i][1]=0;//状态的初始值
    sort(a+1,a+n+1,cmp);//要先排序
    for(int i=2;i<=n;i++)
        for(int j=1;j<i;j++)//枚举上一本书
            for(int l=2;l<=min(i,m);l++)//l表示当前的长度,即状态的第二维
                //由于长度最长就是i,而且只用枚举到n-k,所以上面的min是这样来的
                //至于j,完全不需要担心,因为永远都有j<i
                f[i][l]=min(f[i][l],f[j][l-1]+abs(a[j].w-a[i].w));
    int ans=0x3f3f3f3f;
    for(int i=m;i<=n;i++)//这里要统计答案
        ans=min(ans,f[i][m]);
    printf("%d\n",ans);
    return 0;
}
最后修改日期:2020年3月12日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。