【csp模拟赛4】基站建设 (station.cpp)

【题目描述】

小 Z 的爸爸是一位通信工程师，他所在的通信公司最近接到了一个新的通信工程建设任务，他们需要在 C 城建设一批新的基站。 C 城的城市规划做得非常好，整个城市被规整地划分为 8 行 8 列共 64 个街区，现在已知新基站需要建设在哪些街区，用字符“#”表示，而不需要建设基站的街区用“.”表示。爸爸告诉小 Z 说，建设基站最耗时的是基站两两之间互相通信的调试，每建设一个新的基站，需要确保其与其他已经建好的基站之间能互相通信，若两个基站的坐标分别为(x1,y1)和(x2,y2)，则调试所需时间大概为 max(|x1- x2|,|y1-y2|)，而一个基站的总调试时间为与其他已经建好的基站的调试时间中的最大值。现在爸爸想考考小 Z，看小 Z 能否计算出如何设计建设基站的顺序，使得总的调试时间尽量少？

【输入格式】

输入一个 8 行 8 列的矩阵，全部由“#”和“.”组成。

【输出格式】

输出一个整数，表示花费的最少时间。

【样例输入一】

........

...#....

.#......

.......#

........

【样例输出一】

容易想到，应该“先中间后两边”。更严格地说，现在要把连续的一段格子中的鹅卵石摆放完成，那么把目标位置处于最左边或者最右边的鹅卵石最后放，一定不会更差。下面稍许做些说明：不妨考虑这样一种情况，格子 L~R 中有些格子要放鹅卵石，而且格子 L 和 R 一定要放（下面把目标位置为 x 的鹅卵石称为鹅卵石 x）。假如你给我一个方案，鹅卵石 L 和鹅卵石 R 都不是最后放，那么，把这个方案中鹅卵石 L、R 中后放的那一个与最后放的那个鹅卵石交换顺序，答案不会变差。也就是说，让鹅卵石 L 或者鹅卵石 R 最后放是不会错过最优解的。（如图 2）于是，一维的情况就可以使用区间动态规划，每次决策是让最左边还是让最右边的鹅卵石最后放，剩下的部分就变成了一个子问题。回到原题。由一维的情况，自然地会有如下猜想：放鹅卵石应该“先中间后四周”。或者说，考虑一个矩形区域，(x1, y1)为左上角，(x2, y2)为右下角，那么，考虑让某一条边上的鹅卵石最后放，代价不会变大。仔细想想这也不难说明。（如图 3）这样我们就可以进行动态规划了。枚举把哪一条边上的鹅卵石最后放，余下的便是子问题。

代码：

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cstdio>

using namespace std;

char mp[11][11];

int f[11][11][11][11],tu[11][11];

int jue(int x){return x>0?x:-x;}

int suan(int x1,int y1,int x2,int y2,int i1,int j1,int i2,int j2)

{

	int res=0;

	for(int i=i1;i<=i2;++i)

	for(int j=j1;j<=j2;++j)

	res+=(tu[i][j])*max(max(jue(i-x1),jue(i-x2)),max(jue(j-y1),jue(j-y2)));

	return res;

}

int dfs(int x1,int y1,int x2,int y2)

{

	if(x1>x2||y1>y2)return 0;

	if(f[x1][y1][x2][y2]!=-1) return f[x1][y1][x2][y2];

	int &res = f[x1][y1][x2][y2];

	res = suan(x1,y1,x2,y2,x1,y1,x1,y2)+dfs(x1+1,y1,x2,y2);

	res = min(res,suan(x1,y1,x2,y2,x2,y1,x2,y2)+dfs(x1,y1,x2-1,y2));

	res = min(res,suan(x1,y1,x2,y2,x1,y1,x2,y1)+dfs(x1,y1+1,x2,y2));

	res = min(res,suan(x1,y1,x2,y2,x1,y2,x2,y2)+dfs(x1,y1,x2,y2-1));

	return res;

}

int main()

{

	freopen("station.in","r",stdin);

	freopen("station.out","w",stdout);

	memset(f,-1,sizeof(f));

	for(int i=1;i<=8;++i) scanf("%s",mp[i]+1);

	for(int i=1;i<=8;++i)

		for(int j=1;j<=8;++j)

			tu[i][j] = (mp[i][j]=='#');

	cout << dfs(1,1,8,8);

	fclose(stdin);fclose(stdout);

	return 0;

}

/*

##..####

#####..#

..#.#...

#..##.##

.#.###.#

####.###

#.#...#.

##....#.

168

*/

巴特西

【csp模拟赛4】基站建设 (station.cpp)

最新文章

热门文章