RQNOJ225[书本整理]

动态规划,这次还自己写了个快排。


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


动规方程:f[i][j]=min{f[k][j-1]+abs(book[i].width-book[k].width);k<i}。


边界:f[i][0]=0,f[i][i]=sum{abs(book[j].width-book[j+1].width);j<i},f[i][j]=oo(j>i)。


最后的答案:min{f[i][n-k]}


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);


        }


    int answer=oo;


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


        if (answer>f[i][n-k]) answer=f[i][n-k];


    printf(“%d\n”,answer);


}