GDOI2014 拯救莫莉斯 状压DP

发布于 2017-08-06  6.25k 次阅读


[toggle hide="" title="题目" color=""]

问题描述

莫莉斯·乔是圣域里一个叱咤风云的人物,他凭借着自身超强的经济头脑,牢牢控制了圣域的石油市场。

圣域的地图可以看成是一个n*m的矩阵。每个整数坐标点(x , y)表示一座城市(1<=x<= n, 1<=y<=m)。两座城市间相邻的定义为:对于城市(Ax, Ay)和城市(Bx, By),满足(Ax - Bx)+ (Ay - By)2 = 1。

由于圣域的石油贸易总量很大,莫莉斯意识到不能让每笔石油订购单都从同一个油库里发货。为了提高效率,莫莉斯·乔决定在其中一些城市里建造油库,最终使得每一个城市X都满足下列条件之一:

1.该城市X内建有油库,

2.某城市Y内建有油库,且城市X与城市Y相邻。

与地球类似,圣域里不同城市间的地价可能也会有所不同,所以莫莉斯想让完成目标的总花费尽可能少。如果存在多组方案,为了方便管理,莫莉斯会选择建造较少的油库个数。

输入格式

第一行两个正整数n,m ( n * m <= 50 且m<=n),表示矩阵的大小。

接下来一个n行m列的矩阵F,Fi, j表示在城市(i,j)建造油库的代价。

输出格式

输出两个数,建造方案的油库个数和方案的总代价。

输入样例:

输出样例:

3 3

6 5 4

1 2 3

7 8 9

3 6

数据范围

对于30%数据满足 n * m <= 25;

对于100%数据满足n * m <= 50; 0 <= Fi, j <= 100000

[/toggle]

注意题目是“n*m<=50”,最坏情况应该是7x7的矩阵,显然不能直接暴搜,那么只能用状压DP来做。因为当前一行的状态选择只与其上下两行有关(第一行和最后一行例外),所以设f[i][j][k]表示前i行,i-1行状态为j,i行状态为k时的最优解。枚举行数、i-1行状态、i行状态、i+1行状态,当三行的状态满足要求时,可以更新i+1行的答案,即:$$f_{i+1,k,X}=min{f_{i,j,k}+w_{i+1,X}} .   $$

其中((x|j|k|(j<<1)||(j>>1))&(bit[m]-1)) == bit[m]-1。

最后的答案即为最后一行满足条件的最大值(需枚举) 。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974