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

}