首页 > 其他分享 >P1103 书本整理 (DP)

P1103 书本整理 (DP)

时间:2022-11-04 14:48:01浏览次数:52  
标签:本书 P1103 书架 int 整齐 times dp 书本 DP

书本整理

题目描述

Frank是一个非常喜爱整洁的人。他有一大堆书和一个书架,想要把书放在书架上。书架可以放下所有的书,所以Frank首先将书按高度顺序排列在书架上。但是Frank发现,由于很多书的宽度不同,所以书看起来还是非常不整齐。于是他决定从中拿掉k本书,使得书架可以看起来整齐一点。

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

\(1 \times 2\)
\(5 \times 3\)
\(2 \times 4\)
\(3 \times 1\)
那么Frank将其排列整齐后是:

\(1 \times 2\)
\(2 \times 4\)
\(3 \times 1\)
\(5 \times 3\)
不整齐度就是\(2+3+2=7\)

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

输入格式

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

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

保证高度不重复

输出格式

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

样例 #1

样例输入 #1

4 1
1 2
2 4
3 1
5 3

样例输出 #1

3

解析

对高度进行排序后,高度就没用了,只需要对宽度进行分析。
题目中要求删去k本书,我们可以从反面考虑,即保留多少本书。
设\(dp_{i,j}\)表示枚举到第i本书(且第i本书必须保留)保留了j本书的最小不整齐度,从保留了j-1本书的状态进行转移,即\(dp_{i,j}=min(dp_{t,j-1}+|a[i]-a[t]|)\),其中i从1枚举到n,因为i必须保留,所以j从1开始枚举到min(i,n-k),t从j-1枚举到i-1,最后统计答案即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, k, dp[N][N], b[N];
struct node {
	int x, y;
	bool operator < (const node b) const {
		return x < b.x;
	}
}a[N];
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> k;
	for (int i = 1; i <= n; i ++) cin >> a[i].x >> a[i].y;
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i ++) b[i] = a[i].y;
	memset(dp, 0x3f, sizeof dp);
	for (int i = 0; i <= n; i ++) dp[i][1] = 0;
	for (int i = 1; i <= n; i ++) 
		for (int j = 1; j <= min(i, n - k); j ++)
			for (int t = j - 1; t < i; t ++)
				dp[i][j] = min(dp[i][j], dp[t][j - 1] + abs(b[i] - b[t]));
	int ans = INT_MAX;
	for (int i = n - k; i <= n; i ++) ans = min(ans, dp[i][n - k]);
	cout << ans << '\n';
	return 0;
}

标签:本书,P1103,书架,int,整齐,times,dp,书本,DP
From: https://www.cnblogs.com/YHxo/p/16857704.html

相关文章

  • ThreadPoolExecutor 源码解析
    Java中的线程池是运用场景最多的并发框架,几乎所有需要异步或并发执行任务的程序都可以使用线程池。合理地使用线程池能够带来3个好处:降低资源消耗。通过重复利用已创建的线......
  • Sugoroku 4 (Atcoder abc275 T5) DP
    题目描述题目链接https://atcoder.jp/contests/abc275/tasks/abc275_e题意从\(0\)到\(n\)有\(n+1\)个方格,你现在在第\(0\)个格子。每次移动可以随机走\(1\)......
  • 【DP】动态 DP
    准备退役whk了,最后学点东西。不得不承认,CSPS2022T4对动态DP起到了良好的普及效果。P4719【模板】"动态DP"&动态树分治设\(f_{u,0/1}\)表示不选/选\(u\),\(u\)......
  • gridpanel header click
    varmyGrid=Ext.Create('Ext.grid.Panel',{renderTo:'shrGrid',renderTo:myGrid,store:myStore,//JSONobjectcolumns:myGrid.columns,//JS......
  • DPM(Deformable Part Model)的PCA+Starcasscade(Windows)代码整理
    大家好,我是你们的老朋友——泽哥!最近一直没有写博客是因为泽哥最近在忙本科毕业设计。泽哥的本科毕业设计是研究DPM模型的,相信大家也略微了解,DPM模型即DeformablePartMode......
  • 区间DP
    区间dp\(Part\)\(1\):区间dp?利用一个常见的区间dp问题来寻找其与其他dp的区别。石子合并:先不考虑环上,就只看一条链的情况,要求将\(1\)~\(n\)的石子合并成一颗,每......
  • 使用docker搭建一个WordPress网站
     【整体说明】网站需要三个容器:WordPress、MariaDB、Nginx,他们的关系如下图。这是一个典型的网站,mariadb作为后方的关系型数据库,端口号是3306;wordpress是中间的应用服务......
  • 使用深度强化学习改进POMDP
    论文提出一种ADRQN架构来增强在部分可观测领域的学习表现,架构的特点在于同时考虑动作和观测作为模型的输入。如下图中的模型所示,我们的动作和观测在经过相关的维度变换之......
  • CF1463F Max Correct Set(取小样法+状压 DP)
    CF1463FMaxCorrectSet要求选出集合\(U=\{1,2,3,\dots,n\}\)的一个子集\(S\),满足:如果\(a\inS\)并且\(b\inS\),那么\(|a-b|\not={x}\)并且\(|a-b|\not=......
  • 智能文档处理IDP关键技术与实践-高翔
    什么是智能文档处理?针对文本数据处理尤其是纯文本,大家通常会想到使用自然语言处理(Naturallanguageprocessing,NLP)技术来解决语义理解及分析处理工作。关于自然语言处理技术......