RQNOJ 225 [JSOI2007]书本整理题解

2021-05-18 01:30

阅读：708

标签：去掉 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

样例输出

分析：

哇感觉好难啊...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

上一篇：JSON基础

下一篇：vue.js实现点击后动态添加class及删除同级class

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：RQNOJ 225 [JSOI2007]书本整理题解
文章链接：http://soscw.com/index.php/essay/86978.html

亲，登录后才可以留言！

RQNOJ 225 [JSOI2007]书本整理题解

评论

热门文章

推荐文章

最新文章

置顶文章

RQNOJ 225 [JSOI2007]书本整理 题解

评论

热门文章

推荐文章

最新文章

置顶文章

RQNOJ 225 [JSOI2007]书本整理题解