问题描述
莫莉斯·乔是圣域里一个叱咤风云的人物，他凭借着自身超强的经济头脑，牢牢控制了圣域的石油市场。
圣域的地图可以看成是一个n*m的矩阵。每个整数坐标点(x , y)表示一座城市（1<=x<= n, 1<=y<=m）。两座城市间相邻的定义为：对于城市$(A_x, A_y)$和城市$(B_x, B_y)$，满足$(A_x - B_x)^2 + (A_y - B_y)^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
题解
按照题目的定义，第i行的状态，只会对i-1行至i+1行产生影响
F[i][j][k] 为对于前i行，第i-1行状态为j， 第i行的状态为k，并且对于任意一行x（x<i），该行的所有城市满足题目的要求（附近城市里有油库）
F[i][j][k]的值表示其所能达到的最小代价
（辅助数组G[i][j][k] 表示F[i][j][k]所对应方案里的油库数量）
F[i+1][k][X] = min(F[i][j][k] + cost[i+1][X]); (0 <= X <= 2m )
cost[i][j] 表示第i行，所取状态为j时所需要花费的代价。
转移方程中，X状态可取，需使第i行的所有城市满足要求，即：
(X|j|k|(k<<1)|(k>>1))&(2^m-1)=2^m-1
答案：max(F[n+1][x][0])(0<=X<=2m)
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int F[52][(1 << 8) + 1][(1 << 8) + 1], G[52][(1 << 8) + 1][(1 << 8) + 1];
int a[55][55], n, m, N;
int check(int x, int S)
{
int ans = 0;
for (int i = 1; i <= m; i++)
{
if (((1 << (i - 1)) & S))
ans += a[x][i];
}
return ans;
}
int Get_num(int x)
{
int ans = 0;
while (x)
{
if (x & 1)
ans++;
x >>= 1;
}
return ans;
}
int main()
{
//freopen("proj.in", "r", stdin);
//freopen("proj.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &a[i][j]);
memset(F, 0x3f, sizeof(F));
N = (1 << m) - 1;
for (int i = 0; i <= N; i++)
{
//if ((((i >> 1) | (i << 1) | i) & N) == N)
//{
int ans = check(1, i);
F[1][0][i] = ans;
G[1][0][i] = Get_num(i);
//}
}
for (int i = 1; i <= n; i++)
for (int j = 0; j <= N; j++)
for (int k = 0; k <= N; k++)
for (int m = 0; m <= N; m++)
if (((j | k | m | (k << 1) | (k >> 1)) & (N)) == N)
{
if (F[i][j][k] + check(i + 1, m) < F[i + 1][k][m])
{
F[i + 1][k][m] = F[i][j][k] + check(i + 1, m);
G[i + 1][k][m] = G[i][j][k] + Get_num(m);
}
}
int ans = 0x3f3f3f4f, num = 0;
for (int i = 0; i <= N; i++)
{
if (F[n + 1][i][0] < ans)
{
ans = F[n + 1][i][0];
num = G[n + 1][i][0];
}
else if (F[n + 1][i][0] == ans)
{
if (num > G[n + 1][i][0])
num = G[n + 1][i][0];
}
}
printf("%d %d", num, ans);
//while (1)
;
}