首页 > ACM题库 > HDU-杭电 > hdu 4537 威威猫系列故事――数字分配待解决[解题报告]C++
2015
02-17

hdu 4537 威威猫系列故事――数字分配待解决[解题报告]C++

威威猫系列故事――数字分配

问题描述 :

  住到直角坐标系的威威猫并没有躲开烦恼,难得去晒一次被子,竟然也被洪水冲走了…
  思考再三,威威猫决定报名参军,准备到革命的大熔炉去锻炼自己,于是不久,威威猫就成为了一名光荣的革命军人,并被委派到某边防小岛负责信号站维护工作。

  在这个小岛上有36所信号站,呈矩阵排列,我们把左上角的信号站坐标标注为(0,0),右下角的信号站坐标标注为(5,5).
  每个信号站可以分配1~5个服务频率,来服务周围的用户群.
  可以分配的频率为1~30,由于技术原因,相同或者相邻的频率存在干扰,干扰因素如下:
  
  1.同一个信号站中相同的两个频率会造成无穷大的干扰
  2.同一个信号站中相邻的两个频率会造成A点干扰值
  3.曼哈顿距离为1的两个信号站中如果有两个相同的频率,会造成B点干扰值
  4.曼哈顿距离为1的两个信号站中如果有两个相邻的频率,会造成C点干扰值
  5.曼哈顿距离为2的两个信号站中如果有两个相同的频率,会造成D点干扰值
  6.曼哈顿距离为2的两个信号站中如果有两个相邻的频率,会造成E点干扰值

  一对频率产生的干扰只算一次。

  现在给你各个信号站的初始服务频率分配情况,让你改变(2,2)(2,3)(3,2)(3,3)四个信号站中的服务频率(不能改变频率个数),使得总体的干扰值尽量的小.

输入:

第一行有一个数字T代表有T组数据;
每组数据的第一行有5个数字A B C D E代表上述题目中的干扰值;
接下去有6*6的数据块描述各个信号站的初始频率分配情况;
每个数据块为[n:a1,a2...an]的描述形式,n为该站的服务频率个数,ai表示初始频率分配情况(见sample);

[Technical Specification]
所有数据都是整数
1<=T<=50
1<=A,B,C,D,E<=100
1<=n<=5
1<=ai<=30
数据保证每个信号站初始分配情况不会出现相同的频率

输出:

第一行有一个数字T代表有T组数据;
每组数据的第一行有5个数字A B C D E代表上述题目中的干扰值;
接下去有6*6的数据块描述各个信号站的初始频率分配情况;
每个数据块为[n:a1,a2...an]的描述形式,n为该站的服务频率个数,ai表示初始频率分配情况(见sample);

[Technical Specification]
所有数据都是整数
1<=T<=50
1<=A,B,C,D,E<=100
1<=n<=5
1<=ai<=30
数据保证每个信号站初始分配情况不会出现相同的频率

样例输入:

1
5 4 3 2 1
[1:1][1:2][1:3][1:4][1:5][1:6]
[1:1][1:2][1:3][1:4][1:5][1:6]
[1:1][1:2][5:1,2,3,4,5][5:1,2,3,4,5][1:5][1:6]
[1:1][1:2][5:1,2,3,4,5][5:1,2,3,4,5][1:5][1:6]
[1:1][1:2][1:3][1:4][1:5][1:6]
[1:1][1:2][1:3][1:4][1:5][1:6]

样例输出:

Case #1: 250