题目
展开 题目描述 莫莉斯·乔是圣域里一个叱咤风云的人物，他凭借着自身超强的经济头脑，牢牢控制了圣域的石油市场。
圣域的地图可以看成是一个n*m的矩阵。每个整数坐标点(x , y)表示一座城市（1\le x\le n,1\le y\le m1≤x≤n,1≤y≤m）。两座城市间相邻的定义为：对于城市(Ax, Ay)和城市(Bx, By)，满足(Ax - Bx)^2 + (Ay - By)^2 = 1(Ax−Bx) 2 +(Ay−By) 2 =1。
由于圣域的石油贸易总量很大，莫莉斯意识到不能让每笔石油订购单都从同一个油库里发货。为了提高效率，莫莉斯·乔决定在其中一些城市里建造油库，最终使得每一个城市X都满足下列条件之一：
1.该城市X内建有油库，
2.某城市Y内建有油库，且城市X与城市Y相邻。
与地球类似，圣域里不同城市间的地价可能也会有所不同，所以莫莉斯想让完成目标的总花费尽可能少。如果存在多组方案，为了方便管理，莫莉斯会选择建造较少的油库个数。
输入格式 第一行两个正整数n,m ( n \times m \le 50n×m≤50 且m\le nm≤n)，表示矩阵的大小。
接下来一个n行m列的矩阵F，F_{i, j}F i,j 表示在城市(i,j)建造油库的代价。
输出格式 输出两个数，建造方案的油库个数和方案的总代价。
输入输出样例 输入 #1复制 3 3 6 5 4 1 2 3 7 8 9 输出 #1复制 3 6 说明/提示 对于30%数据满足 n \times m \le 25n×m≤25;
对于100%数据满足n \times m \le 50,0 \le F_{i, j} \le 100000n×m≤50,0≤F i,j ≤100000
思路
状压dp 设f[i][j][k]为第i行，第i行的状态为j，第i-1行的状态为k的最小代价 转移条件是：j∣k∣p∣(j≪1)∣(j≫1)&(2m−1)==(2m−1)
代码
#include<bits/stdc++.h>
using namespace std
;
int n
,m
;
int map
[51][51];
int dp
[51][129][129],s
[51][129][129];
int val
[51][129],num
[129];
int read()
{
char c
=getchar();
int x
=0;
while(c
<'0'||c
>'9') c
=getchar();
while(c
>='0'&&c
<='9')
x
=(x
<<3)+(x
<<1)+c
-48,c
=getchar();
return x
;
}
int logg(int x
)
{
int tot
=0;
while(x
) tot
++,x
>>=1;
return tot
;
}
int cnt(int x
)
{
int tot
=0;
while(x
) tot
++,x
-=lowbit(x
);
return tot
;
}
int M
;
int solve(int x
)
{
return M
&(((x
<<1)|x
)|((x
>>1)|x
));
}
void merge(int a
,int b
,int c
,int v
,int t
,int x
,int y
,int z
)
{
if(dp
[a
][b
][c
]+v
>dp
[x
][y
][z
]) return;
if(dp
[a
][b
][c
]+v
<dp
[x
][y
][z
])
{
dp
[x
][y
][z
]=dp
[a
][b
][c
]+v
;
s
[x
][y
][z
]=s
[a
][b
][c
]+t
;
return;
}
s
[x
][y
][z
]=min(s
[x
][y
][z
],s
[a
][b
][c
]+t
);
}
int main()
{
n
=read(),m
=read();
for(int i
=1; i
<=n
; i
++)
for(int j
=1; j
<=m
; j
++)
map
[i
][j
]=read();
M
=(1<<m
)-1;
for(int i
=1; i
<=n
; i
++)
for(int j
=1; j
<=M
; j
++)
val
[i
][j
]=val
[i
][j
-lowbit(j
)]+map
[i
][logg(lowbit(j
))];
for(int i
=1; i
<=M
; i
++) num
[i
]=cnt(i
);
memset(dp
,20,sizeof(dp
));
for(int i
=0; i
<=M
; i
++)
dp
[1][i
][solve(i
)]=min(dp
[1][i
][solve(i
)],val
[1][i
]),s
[1][i
][solve(i
)]=num
[i
];
for(int i
=2; i
<=n
; i
++)
{
for(int j
=0; j
<=M
; j
++)
{
int p
=M
^j
;
for(int k
=p
; k
; k
=(k
-1)&p
)
{
if(dp
[i
-1][j
][k
|j
]==336860180) continue;
int d
=k
|j
,s
=M
^d
;
for(int t
=d
; t
; t
=(t
-1)&d
)
merge(i
-1,j
,d
,val
[i
][s
]+val
[i
][t
],num
[s
]+num
[t
],i
,t
|s
,j
|solve(t
)|solve(s
));
merge(i
-1,j
,d
,val
[i
][s
],num
[s
],i
,s
,j
|solve(s
));
}
for(int k
=0; k
>-1; k
--)
{
if(dp
[i
-1][j
][k
|j
]==336860180) continue;
int d
=k
|j
,s
=M
^d
;
for(int t
=d
; t
; t
=(t
-1)&d
)
merge(i
-1,j
,d
,val
[i
][s
]+val
[i
][t
],num
[s
]+num
[t
],i
,t
|s
,j
|solve(t
)|solve(s
));
merge(i
-1,j
,d
,val
[i
][s
],num
[s
],i
,s
,j
|solve(s
));
}
}
}
int ans
=999999999;
for(int i
=0; i
<=M
; i
++)
ans
=min(ans
,dp
[n
][i
][M
]);
int T
=999999999;
for(int i
=0; i
<=M
; i
++)
if(dp
[n
][i
][M
]==ans
) T
=min(T
,s
[n
][i
][M
]);
printf("%d %d\n",T
,ans
);
return 0;
}
