此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。
题目链接：http://www.rqnoj.cn/problem/225
Frank是一个非常喜爱整洁的人。他有一大堆书和一个书架，想要把书放在书架上。
书架可以放下所有的书，所以Frank首先将书按高度顺序排列在书架上。
但是Frank发现，由于很多书的宽度不同，所以书看起来还是非常不整齐。于是他决定从中拿掉k本书，使得书架可以看起来整齐一点。
书架的不整齐度是这样定义的：每两本书宽度的差的绝对值的和。例如有4本书：
1x2
5x3
2x4
3x1
那么Frank将其排列整齐后是：
1x2
2x4
3x1
5x3
不整齐度就是2+3+2=7
已知每本书的高度都不一样，请你求出去掉k本书后的最小的不整齐度。
第一行两个数字n和k，代表书有几本，从中去掉几本。(1<=n<=100, 1<=k<n)
下面的n行，每行两个数字表示一本书的高度和宽度，均小于200。
一行一个整数，表示书架的最小不整齐度。
样例输入
1 2
2 4
3 1
5 3
样例输出
3
分析：
哇感觉好难啊...dalao说这是划分DP...反正窝啥DP都不会的T.T主要是理解不了为啥要三维。
正着做应该也可做，但是反过来更好理解一些，也就是把拿出k本转化为留下n-k本。
dp[i][j]表示前i本书中选择j本，其中第i本必选的最小不整齐度。
再枚举一个x，x的范围是[j-1,i-1],表示第x本书取/不取，取的话就是dp[x][j-1]+abs(a[i].w-a[x].w),不取的话就是dp[i][j].
最终的ans就是Min(dp[n-k...n][n-k])
AC代码：
1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 #include<cstring> 5 ?6 const int MAXN = 110; 7 const int INF = 2147483645; 8 inline void read(int &x) 9 {10 ????char ch = getchar(),c = ch;x = 0;11 ????while(ch < ‘0‘ || ch > ‘9‘) c = ch,ch = getchar();12 ????while(ch <= ‘9‘ && ch >= ‘0‘) x = (x<<1)+(x<<3)+ch-‘0‘,ch = getchar();13 ????if(c == ‘-‘) x = -x;14 }15 16 int n,k,ans;17 int dp[MAXN][MAXN];18 19 struct BOOK20 {21 ????int h,w;22 }a[MAXN];23 24 int cmp(BOOK a,BOOK b)25 {return a.h < b.h;}26 27 inline int Min(int a,int b)28 {return a<b?a:b;}29 30 inline int Abs(int x)31 {return x>=0?x:-x;}32 33 int main()34 {35 ????read(n),read(k);36 ????for(int i = 1;i <= n;++ i)37 ????????read(a[i].h),read(a[i].w);38 ????std::sort(a+1,a+1+n,cmp);39 ????for(int i = 1;i <= n;++ i)40 ????????for(int j = 2;j <= Min(i,n-k);++ j)41 ????????{42 ????????????dp[i][j] = INF;43 ????????????for(int x = j-1;x <= i-1;++ x)44 ????????????????dp[i][j] = Min(dp[i][j],dp[x][j-1]+Abs(a[x].w-a[i].w));45 ????????}46 ????ans = dp[n][n-k];47 ????for(int i = n-k;i <= n;++ i)48 ????????ans = Min(ans,dp[i][n-k]);49 ????printf("%d\n",ans);50 ????return 0;51 }RQNOJ 225 [JSOI2007]书本整理 题解
原文地址：http://www.cnblogs.com/shingen/p/7739716.html