首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C语言 >

一道ACM的题目。该怎么处理

2012-06-11 
一道ACM的题目。座位调整题目描述:百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现,员工如

一道ACM的题目。
座位调整 

题目描述: 

百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现,员工如果可以在自己喜欢的美食旁边工作,工作效率会大大提高。因此,百度决定进行一次员工座位的大调整。 

调整的方法如下: 

1 . 首先将办公区按照各种零食的摆放分成 N 个不同的区域。(例如:可乐区,饼干区,牛奶区等等)。 

2 . 每个员工对不同的零食区域有不同的喜好程度(喜好程度度的范围为 1 — 100 的整数, 喜好程度越大表示该员工越希望被调整到相应的零食区域)。 

3 . 由于每个零食区域可以容纳的员工数量有限,人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。 

数据输入: 

第一行包含两个整数 N , M ,( 1<=N , M<=300 )。分别表示 N 个区域和 M 个员工。 

第二行是 N 个整数构成的数列 a ,其中 a[i] 表示第 i 个区域可以容纳的员工数, (1<=a[i]<=M , a[1]+a[2]+..+a[N]=M) 。 

紧接着是一个 M*N 的矩阵 P , P ( i , j )表示第 i 个员工对第 j 个区域的喜好度。 

答案输出: 

对于每个测试数据,输出可以达到的最大的喜好程度。 

输入样例


3 3 

1 1 1 

100 50 25 

100 50 25 

100 50 25 




输出样例


175 




谁能告诉我这个题目的算法思路么?

[解决办法]
这是《编程之美》里的一道原题,公司换成了baidu。
[解决办法]

探讨

引用:
这是《编程之美》里的一道原题,公司换成了baidu。

能给我讲讲这道题目的算法思路么。

[解决办法]
http://www.baidu.com/s?wd=acm+%D7%F9%CE%BB%B5%F7%D5%FB&opt-webpage=on&ie=gbk

热点排行