一、题目
二、解题思路
1.首先需要将书根据高进行排序。发现书的高度唯一，因此我们可以采用map进行书的存储，存储完毕后，书将会自动有序。
2.考虑到前面的书拿掉时不会对后面的结果产生影响，因此可以想到该题可用动态规划进行求解。
3.应当注意的是，在动规时，应当保存每本书的状态（第i本书是否保留，因为如果不保留的话，无法计算第i本书以后的不整齐度），此时规定dp[k][i][0]表示对于前i本书，当不保留第i本书时，拿走k本书后的最优值；dp[k][i][1]表示对于前i本书，当保留第i本书时，拿走k本书后的最优值。假设我们未保留每本书的状态，令dp[k][i]表示对于前i本书，拿走k本书后的最优值，显然，此时无法计算dp[k][i+1]的值，因为我们不知道前i本书中，到底哪些书被保留了，那也就无法计算不整齐度。
4.对于dp[k][i][0]的计算，我们只需要关注当前i-1本书中，拿掉k-1本书后的最优值即可，至于第i-1本书是否被拿掉，都不影响最终结果，因为新加的书直接被拿掉，相当于没加。则dp[k][i][0]=min(dp[k-1][i-1][0],dp[k-1][i-1][1])；而对于dp[k][i][1]的计算则稍微复杂点，我们需要找到最近被保留的那本书，才可以计算保留第i本书后，新的不整齐度变为多少，此时可采用遍历的方法，从最靠近i的书开始遍历，值得注意的是，每往前移动一位，拿掉的书应该多一本，具体来说，当我们假设最近保留的书为i-1时，那我们只需要得到dp[k][i-1][1]的结果即可得到此时dp[k][i][1]的结果；当最近保留的书为i-2时，我们需要得到dp[k-1][i-2][1]的结果，而非dp[k][i-2][1]，因为当最近保留的书为i-2时，相当于默认把第i-1本书拿掉了。
三、代码
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
int n,k;
int dp[201][201][2]={0};
cin>>n>>k;
map<int, int> books;
for(int i=0;i<n;i++){
int h,w;
cin>>h>>w;
books[h]=w;
}
vector<int> weights(1, 0);
map<int, int>::iterator it=books.begin();
while(it!=books.end()){
weights.push_back(it->second);
it++;
}
//初始化动规数组
int irregularity=0;
for(int i=2;i<=n;i++){
irregularity+=abs(weights[i]-weights[i-1]);
//dp[k][n][0]表示前n个中，当不保留第n本书时，拿掉k本书的最优值
//dp[k][n][1]表示前n个中，当保留第n本书时，拿掉k本书的最优值
dp[0][i][1]=irregularity;
}
for(int i=2;i<=n;i++){
dp[1][i][0]=dp[0][i][1]-abs(weights[i]-weights[i-1]);
dp[1][i][1]=irregularity;
if(i==2){
dp[1][i][1]=0;
continue;
}
for(int k=i-1;k>=i-2;k--){
dp[1][i][1]=min(dp[1][i][1], dp[2-(i-k)][k][1]+abs(weights[i]-weights[k]));
}
}
for(int i=2;i<=k;i++){
//当j和i的差值小于2时，结果必然为0，因为此时最多只剩下一本书
for(int j=i+2;j<=n;j++){
//计算前n个中，当不保留第n本书时，拿掉k本书的最优值
dp[i][j][0]=min(dp[i-1][j-1][0], dp[i-1][j-1][1]);
//计算前n个中，当保留第n本书时，拿掉k本书的最优值
dp[i][j][1]=irregularity;
for(int k=j-1;k>=j-i-1;k--){
dp[i][j][1]=min(dp[i][j][1], dp[i-(j-1-k)][k][1]+abs(weights[j]- weights[k]));
}
}
}
cout<<min(dp[k][n][1], dp[k][n][0]);
}
