题目描述
Frank是一个非常喜爱整洁的人。他有一大堆书和一个书架，想要把书放在书架上。书架可以放下所有的书，所以Frank首先将书按高度顺序排列在书架上。但是Frank发现，由于很多书的宽度不同，所以书看起来还是非常不整齐。于是他决定从中拿掉k本书，使得书架可以看起来整齐一点。 书架的不整齐度是这样定义的：每两本书宽度的差的绝对值的和。例如有4本书：1x2 5x3 2x4 3x1 那么Frank将其排列整齐后是：1x2 2x4 3x1 5x3 不整齐度就是2+3+2=7 已知每本书的高度都不一样，请你求出去掉k本书后的最小的不整齐度。
输入格式：
第一行两个数字n和k，代表书有几本，从中去掉几本 下面的n行，每行两个数字表示一本书的高度和宽度，均小于200。 保证高度不重复
输出格式：
一行一个整数，表示书架的最小不整齐度。
数据范围：
(1<=n<=100）
一道典型的dp题。虽然是普及-，但向来不会做dp的我愣是没想出正解。本来令f[i][j]表示推到了第i号书（咸鱼的想法：dp没思路就设f[i][j]），前面已经抽掉了j本，考虑第i本书抽不抽。但死活没想出转移方程来。后来看了题解才恍然大悟，原来问题可以转化成放入n-k本书，求混乱程度。这样我们令f[i][j]表示插入了i本书，其中最后一本是j，转移方程就是f[i][j]=min{f[i-1][e]} (i-1<=e<=j-1)。
这个故事告诉我们，dp题很狡猾，正着想不出来那就倒着想，就像【P1280 尼克的任务】。
代码如下：
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<algorithm> using namespace std; struct node{ int h,w; }a[110]; int f[101][101]; bool cmp(node a,node b) { return a.h>b.h; } int main() { int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].h,&a[i].w); } sort(a+1,a+n+1,cmp); memset(f,0x7f,sizeof(f)); for(int i=1;i<=n;i++) { f[1][i]=0; } for(int i=1;i<=n-k;i++) { for(int j=i;j<=n;j++) { for(int k=i-1;k<j;k++) { f[i][j]=min(f[i][j],f[i-1][k]+abs(a[j].w-a[k].w)); } } } int minn=1e9; for(int i=1;i<=n;i++) { minn=min(minn,f[n-k][i]); } printf("%d",minn); return 0; }ps：蒟蒻还要努力刷dp，毕竟pty大神还刷了200道dp才入门呢。noip肯定有至少一百分 不要白不要
