问题描述#

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

圣域的地图可以看成是一个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)
    ;
}