洛谷——P1103 书本整理
2024-08-25 03:48:34
https://www.luogu.org/problem/show?pid=1103
题目描述
Frank是一个非常喜爱整洁的人。他有一大堆书和一个书架,想要把书放在书架上。书架可以放下所有的书,所以Frank首先将书按高度顺序排列在书架上。但是Frank发现,由于很多书的宽度不同,所以书看起来还是非常不整齐。于是他决定从中拿掉k本书,使得书架可以看起来整齐一点。
书架的不整齐度是这样定义的:每两本书宽度的差的绝对值的和。例如有4本书:
1x2 5x3 2x4 3x1 那么Frank将其排列整齐后是:
1x2 2x4 3x1 5x3 不整齐度就是2+3+2=7
已知每本书的高度都不一样,请你求出去掉k本书后的最小的不整齐度。
输入输出格式
输入格式:
第一行两个数字n和k,代表书有几本,从中去掉几本。(1<=n<=100, 1<=k<n)
下面的n行,每行两个数字表示一本书的高度和宽度,均小于200。
保证高度不重复
输出格式:
一行一个整数,表示书架的最小不整齐度。
输入输出样例
输入样例#1:
4 1
1 2
2 4
3 1
5 3
输出样例#1:
3 先以高度排序,
拿走K本看做只选n-k本,f[i][j]表示前i本中,一定有第i本,且已经选了j本、
则f[i][j]=min{ f[t][j-1]+abs(w[i]-w[t] }
#include <algorithm>
#include <cstdlib>
#include <cstdio> #define min(a,b) (a<b?a:b)
inline void read(int &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
}
const int N();
int n,k,f[N][N];
struct Node {
int h,w;
bool operator < (const Node x) const
{
return h<x.h;
}
}book[N]; int Presist()
{
read(n),read(k);k=n-k;
for(int i=; i<=n; ++i)
read(book[i].h),read(book[i].w);
std::sort(book+,book+n+);
int ans=0x3f3f3f3f;
for(int i=; i<=n; ++i)
{
for(int j=; j<=min(i,k); ++j)
{
f[i][j]=0x3f3f3f3f;
for(int t=j-; t<i; ++t)
f[i][j]=min(f[i][j],f[t][j-]+abs(book[i].w-book[t].w));
}
if(i>=k) ans=min(ans,f[i][k]);
}
printf("%d\n",ans);
return ;
} int Aptal=Presist();
int main(){;}
最新文章
- 单机搭建Android开发环境(四)
- AC自动机(1)
- 信息安全系统设计基础exp_1
- [转]Redis集群的配置
- ros与下位机通信常用的c++ boost串口应用--22
- CSS之生成全屏背景图片
- Django 1.6 的测试驱动开发
- HDU-2031-进制转换
- 与64位版本的Windows不兼容,masm运行不了
- Alpha冲刺博客合集
- DOS的重定向命令及在安全方面的应用
- 你了解大O符号(big-O notation)么?你能给出不同数据结构的例子么?
- https加载非https资源时不出现问题
- Python-集合-17
- A1069. The Black Hole of Numbers
- Flutter学习笔记与整合
- 前端开发 - jQuery
- KNN算法的R语言实现
- 【我的Android进阶之旅】 RxJava 理解Backpressure并解决异常 rx.exceptions.MissingBackpressureException
- Linux服务管理 systemctl命令详解
热门文章
- codechef : TREDEG , Trees and Degrees
- [ZJOI2006]Book书架
- ACM_01背包(恰好装满)
- Shell脚本,简单&; 强大
- mvc使用linq to sql进行sum统计遇到查询为null的问题
- Anniversary Cake
- Java8(一)--lambda表达式
- Linux kernel 内存 - 页表映射(SHIFT,SIZE,MASK)和转换(32位,64位)
- Maya Calendar POJ - 1008 (模拟)
- [不断更新中] 各种错误&;&;总结