#include<bits/stdc++.h>
using namespace std;
struct book{
int h,w;
}arr[105];
int n,m,dp[105][105];
bool cmp(book &s1,book &s2){
return s1.h<s2.h;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>arr[i].h>>arr[i].w;
}
sort(arr+1,arr+1+n,cmp);
m=n-m;
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++){
dp[i][1]=0;
for(int j=1;j<i;j++){
for(int k=1;k<=min(j,m-1);k++){
dp[i][k+1]=min(dp[i][k+1],dp[j][k]+abs(arr[i].w-arr[j].w));
}
}
}
int ans=0x3f3f3f;
for(int i=1;i<=n;i++){
ans=min(ans,dp[i][m]);
}
cout<<ans;
return 0;
}
0x3f的十进制是63,开始时我的ans初始化为0x3f,所以有的点一直输出63。 我写代码时一直用memset(dp,0x3f,sizeof(dp));而不出错,原因在于memset这个函数是对每个字节赋值,所以dp中的元素大小为0x3f3f3f3f,这个数足够大而没出错,而单纯将一个整型赋值为0x3f会过小。
今天也是给我上了一课。