座位调整

题目描述：

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

调整的方法如下：

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

数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为100+50+25=175

来自：http://hi.baidu.com/astar/blog/item/5e074c08fdd782940a7b82be.html

分类： IT竞赛比赛 培训考证