P1103 书本整理【洛谷算法习题】

P1103 书本整理网页链接P1103 书本整理题目描述Frank 是一个非常喜爱整洁的人。他有一大堆书和一个书架想要把书放在书架上。书架可以放下所有的书所以 Frank 首先将书按高度顺序排列在书架上。但是 Frank 发现由于很多书的宽度不同所以书看起来还是非常不整齐。于是他决定从中拿掉k kk本书使得书架可以看起来整齐一点。书架的不整齐度是这样定义的每两本书宽度的差的绝对值的和。例如有4 44本书1 × 2 1 \times 21×25 × 3 5 \times 35×32 × 4 2 \times 42×43 × 1 3 \times 13×1那么 Frank 将其排列整齐后是1 × 2 1 \times 21×22 × 4 2 \times 42×43 × 1 3 \times 13×15 × 3 5 \times 35×3不整齐度就是2 3 2 7 23272327。已知每本书的高度都不一样请你求出去掉k kk本书后的最小的不整齐度。输入格式第一行两个数字n nn和k kk代表书有几本从中去掉几本1 ≤ n ≤ 100 , 1 ≤ k n 1 \le n \le 100, 1 \le kn1≤n≤100,1≤kn。下面的n nn行每行两个数字表示一本书的高度和宽度均小于等于200 200200。保证高度不重复。输出格式一行一个整数表示书架的最小不整齐度。输入输出样例 #1输入 #14 1 1 2 2 4 3 1 5 3输出 #13解题思路本题核心是排序动态规划求解最小不整齐度由于书本必须按高度排列先将所有书按高度升序排序问题转化为从n本书中选出mn-k本使相邻宽度差绝对值之和最小。定义dp[i][j]为前i本书选j本、且第j本为第i本书的最小不整齐度。状态转移时枚举上一本选中的书k累加宽度差代价取最小值。初始化边界状态后遍历所有以任意书为结尾的选m本的方案最终得到全局最小值。算法时间复杂度O(n²m)完美适配n≤100的数据范围。总结核心逻辑将书本按高度排序用动态规划选择指定数量的书本最小化相邻宽度差的总和。关键操作排序预处理二维DP状态转移枚举前驱节点计算不整齐度代价。效率保障数据规模极小三重循环计算无压力能够快速得到最优解。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e310;constll p1e97;constll INF1e18;constll M5e310;ll f[110][110];structNode{ll h,l;}s[110];boolcmp(constNodea,constNodeb){returna.hb.h;}intmain(){ll n,m;cinnm;mn-m;for(ll i1;in;i)cins[i].hs[i].l;sort(s1,sn1,cmp);for(ll i2;in;i)for(ll j2;jmin(i,m);j){f[i][j]2147483647;for(ll kj-1;ki;k)f[i][j]min(f[i][j],f[k][j-1]abs(s[i].l-s[k].l));}ll ans2147483647;for(ll im;in;i)ansmin(ans,f[i][m]);coutansendl;return0;}