RQNOJ 225 [JSOI2007]书本整理 题解

2021-05-18 01:30

阅读:717

标签:去掉   16px   return   选择   cstring   col   turn   logs   for   

此文为博主原创题解,转载时请通知博主,并把原文链接放在正文醒目位置。

题目链接:http://www.rqnoj.cn/problem/225

 

题目描述

Frank是一个非常喜爱整洁的人。他有一大堆书和一个书架,想要把书放在书架上。

书架可以放下所有的书,所以Frank首先将书按高度顺序排列在书架上。

但是Frank发现,由于很多书的宽度不同,所以书看起来还是非常不整齐。于是他决定从中拿掉k本书,使得书架可以看起来整齐一点。

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

1x2

5x3

2x4

3x1

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

1x2

2x4

3x1

5x3

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

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

 

输入格式

第一行两个数字n和k,代表书有几本,从中去掉几本。(1

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

 

输出格式

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

样例输入

1 2
2 4
3 1
5 3

样例输出

3

 

分析:

哇感觉好难啊...dalao说这是划分DP...反正窝啥DP都不会的T.T主要是理解不了为啥要三维。

正着做应该也可做,但是反过来更好理解一些,也就是把拿出k本转化为留下n-k本。

dp[i][j]表示前i本书中选择j本,其中第i本必选的最小不整齐度。

再枚举一个x,x的范围是[j-1,i-1],表示第x本书取/不取,取的话就是dp[x][j-1]+abs(a[i].w-a[x].w),不取的话就是dp[i][j].

最终的ans就是Min(dp[n-k...n][n-k])

 

AC代码:

 1 #include 2 #include
 3 #include 4 #include 5 
 6 const int MAXN = 110;
 7 const int INF = 2147483645;
 8 inline void read(int &x)
 9 {
10     char ch = getchar(),c = ch;x = 0;
11     while(ch ‘0 || ch > 9) c = ch,ch = getchar();
12     while(ch ‘9 && ch >= 0) x = (x1)+(x3)+ch-0,ch = getchar();
13     if(c == -) x = -x;
14 }
15 
16 int n,k,ans;
17 int dp[MAXN][MAXN];
18 
19 struct BOOK
20 {
21     int h,w;
22 }a[MAXN];
23 
24 int cmp(BOOK a,BOOK b)
25 {return a.h  b.h;}
26 
27 inline int Min(int a,int b)
28 {return aa:b;}
29 
30 inline int Abs(int x)
31 {return x>=0?x:-x;}
32 
33 int main()
34 {
35     read(n),read(k);
36     for(int i = 1;i  i)
37         read(a[i].h),read(a[i].w);
38     std::sort(a+1,a+1+n,cmp);
39     for(int i = 1;i  i)
40         for(int j = 2;j  j)
41         {
42             dp[i][j] = INF;
43             for(int x = j-1;x 1;++ x)
44                 dp[i][j] = Min(dp[i][j],dp[x][j-1]+Abs(a[x].w-a[i].w));
45         }
46     ans = dp[n][n-k];
47     for(int i = n-k;i  i)
48         ans = Min(ans,dp[i][n-k]);
49     printf("%d\n",ans);
50     return 0;
51 }

 

 

 

RQNOJ 225 [JSOI2007]书本整理 题解

标签:去掉   16px   return   选择   cstring   col   turn   logs   for   

原文地址:http://www.cnblogs.com/shingen/p/7739716.html


评论


亲,登录后才可以留言!