# RQNOJ225[书本整理]

f[i][j]表示前i本中已经选了j本，并且最后一本选的是i时的最优值。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-24

DESCRIPTION:

http://www.rqnoj.cn/Problem_225.html

[JSOI2007]书本整理

*/

#include <stdio.h>

#include <stdlib.h>

const int oo=(~0u)>>2;

const int MAXN=100;

struct Book{int h,w;};

int n,k;

Book book[MAXN+2];

int f[MAXN+2][MAXN+2];

void quick_sort(int L,int R)

{

int i=L,j=R;

Book mid=book[(L+R)>>1],swap;

while (i<=j)

{

while (book[i].h<mid.h) i++;

while (book[j].h>mid.h) j–;

if (i<=j)

swap=book[i],book[i]=book[j],book[j]=swap,

i++,j–;

}

if (L<j) quick_sort(L,j);

if (i<R) quick_sort(i,R);

}

int main()

{

scanf(“%d%d”,&n,&k);

for (int i=1;i<=n;i++) scanf(“%d%d”,&book[i].h,&book[i].w);

quick_sort(1,n);

for (int i=1;i<=n;i++)

for (int j=0;j<=n;j++)

f[i][j]=oo;

for (int i=1;i<=n;i++)

for (int j=0;j<=i;j++)

{

if (j==0) f[i][j]=0;

else if (j==i) f[i][j]=i>1?f[i-1][j-1]+abs(book[i].w-book[i-1].w):0;

else for (int ii=1,jj=j-1;ii<i;ii++)

f[i][j]<?=f[ii][jj]+(jj?abs(book[i].w-book[ii].w):0);

}

for (int i=1;i<=n;i++)