P1103 书本整理

技巧比较强，如果正着想删除几本书那实在是太难了，我是白给了。倒着想留下几本书的话，我们可以判断当前书在序列中是留下的第几本，那么很容易想到每一本都有可能由前面的任意序列组合而成，最后再枚举第三个剩下的条件然后即可解决

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int h,w;
}a[105];
int f[105][105],n,m,ans=1<<30;
bool cmp(node a,node b)
{
    return a.h<b.h;
}
int main()
{
    memset(f,0x3f,sizeof(f));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    f[i][1]=0;
    m=n-m;
    for(int i=1;i<=n;i++)
    scanf("%d%d",&a[i].h,&a[i].w);
    sort(a+1,a+1+n,cmp);
    for(int i=2;i<=n;i++)
    for(int j=1;j<i;j++)
    for(int k=2;k<=min(m,i);k++)
    f[i][k]=min(f[i][k],f[j][k-1]+abs(a[i].w-a[j].w));
    for(int i=m;i<=n;i++)
    ans=min(ans,f[i][m]);
    printf("%d",ans);
}