P1103 书本整理 区间dp

　　

题目描述

Frank是一个非常喜爱整洁的人。他有一大堆书和一个书架，想要把书放在书架上。书架可以放下所有的书，所以Frank首先将书按高度顺序排列在书架上。但是Frank发现，由于很多书的宽度不同，所以书看起来还是非常不整齐。于是他决定从中拿掉k本书，使得书架可以看起来整齐一点。

书架的不整齐度是这样定义的：每两本书宽度的差的绝对值的和。例如有4本书：

1 imes 21×2
5 imes 35×3
2 imes 42×4
3 imes 13×1
那么Frank将其排列整齐后是：

1 imes 21×2
2 imes 42×4
3 imes 13×1
5 imes 35×3
不整齐度就是2+3+2=72+3+2=7

已知每本书的高度都不一样，请你求出去掉k本书后的最小的不整齐度。

输入输出格式

输入格式：

第一行两个数字nn和kk，代表书有几本，从中去掉几本。(1 le n le 100, 1 le k<n1≤n≤100,1≤k<n)

下面的nn行，每行两个数字表示一本书的高度和宽度，均小于200200。

保证高度不重复

输出格式：

一行一个整数，表示书架的最小不整齐度。

输入输出样例

输入样例#1： 复制

4 1
1 2
2 4
3 1
5 3

输出样例#1： 复制

3

很明显是区间dp
但是不能直接的删除k个   要改为选择n-k个 比较方便
注意三重循环的细节

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
#define lson l,m,pos<<1
#define rson m+1,r,pos<<1|1
const int N=210;
int dp[N][N];

struct node
{
    int v,h;
}a[N];
bool cmp(node a,node b){return a.h<b.h;}
int main()
{
    int n,k;RII(n,k);
    k=n-k;

    rep(i,1,n)
    RII(a[i].h,a[i].v);
    sort(a+1,a+1+n,cmp);
    CLR(dp,0x3f);

    rep(i,1,n)
    dp[i][1]=0;

    rep(i,2,n)
    rep(j,2,min(i,k))
    rep(s,j-1,i-1)//注意这里一定是从j-1开始  因为是从 j-1 递推到j的！！  
    dp[i][j]=min(dp[i][j], dp[s][j-1]+abs( a[i].v-a[s].v ) );

    int ans=inf;
    rep(i,k,n)//注意答案不是dp[n][k]
    ans=min(ans,dp[i][k]);

    cout<<ans;

    return 0;
}