洛谷 P1103 书本整理

原题

题目描述

对于给出的书本，Frank会先把它们按照高度排好序，接下来通过删去k本书来达到最小的不整齐度。

解题思路

我们可以令f[i][j]表示当有i本书时，留下j本的最小不整齐度。通过稍微地分析，我们就可以得到f[i][k1]=min(f[i][k1],f[j][k1-1]+abs(a[i].k-a[j].k));其中，i为当前有多少本书；k1为留下的本数。

#include<bits/stdc++.h> using namespace std; struct node{ int h,k; }a[110]; int f[110][110]; bool cmp(node a1,node a2){ return a1.h>a2.h; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,k; cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i].h>>a[i].k; } sort(a+1,a+n+1,cmp); //按照高度进行排序 fill(f[1]+1,f[n+1],0x3f3f3f3f); //将f数组初始化为∞ for(int i=1;i<=n;i++)f[i][1]=0; //只留1本不整齐度为0 for(int i=2;i<=n;i++){ for(int j=1;j<=i-1;j++){ for(int k1=2;k1<=min(i,n-k)/*枚举留下k1本书*/;k1++){ f[i][k1]=min(f[i][k1],f[j][k1-1]+abs(a[i].k-a[j].k)); } } } int ans=INT_MAX; for(int i=n-k;i<=n;i++){ ans=min(ans,f[i][n-k]); //选取最小值 } cout<<ans; return 0; }