注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

RQNOJ225[书本整理]  

2010-07-24 11:32:46|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

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

}

 

  评论这张
 
阅读(227)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018