Frank是一個非常喜愛整潔的人。他有一大堆書和一個書架,想要把書放在書架上。書架可以放下所有的書,是以Frank首先将書按高度順序排列在書架上。但是Frank發現,由于很多書的寬度不同,是以書看起來還是非常不整齊。于是他決定從中拿掉k本書,使得書架可以看起來整齊一點。
書架的不整齊度是這樣定義的:每兩本書寬度的差的絕對值的和。例如有4本書:
1x25x32x43x1那麼Frank将其排列整齊後是:
1x22x43x15x3不整齊度就是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
直接從去掉多少書來劃分階段是沒有思路的。
可以把問題轉化成求在n本書中選出n-k本書的最小值。
設f[i,j]表示在前i本書選j本書的最小值。
f[i,j]=min{f[l,j-1]+abs(w[i]-w[l])} (1<=i<=n,2<=j<=min{i,n-k},j-1<=l<=i-1)
則ans=min{f[i,n-k]} (n-k<=i<=n)
#include<bits/stdc++.h>
using namespace std;//a[i][j]表示前i本書保留j本的最小值 ,第i本不替換
struct node{
int x;
int y;
}h[201];
bool comp(node a,node b)
{
return a.x<b.x;
}
int main()
{ int m,n,k,f[200][200];
int ans=2147483647;
cin>>n>>k;m=n-k;
for(int i=1;i<=n;i++)
cin>>h[i].x>>h[i].y;
sort(h+1,h+1+n,comp);
for(int i=2;i<=n;i++)
for(int j=2;j<=min(m,i);j++)
{f[i][j]=2147483647;
for(int k=j-1;k<i;k++)
f[i][j]=min(f[i][j],f[k][j-1]+abs(h[k].y-h[i].y));//好神奇!!因為前k本書已保留了j-1本,第i本也保留 ,正好j本
}
for(int i=m;i<=n;i++)
ans=min(ans,f[i][m]);
cout<<ans;
}