[GDOI2014] 拯救莫莉斯

问题描述#

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

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

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
using namespace std;
5
int F[52][(1 << 8) + 1][(1 << 8) + 1], G[52][(1 << 8) + 1][(1 << 8) + 1];
6
int a[55][55], n, m, N;
7
int check(int x, int S)
8
{
9
    int ans = 0;
10
    for (int i = 1; i <= m; i++)
11
    {
12
        if (((1 << (i - 1)) & S))
13
            ans += a[x][i];
14
    }
15
    return ans;
16
}
17
int Get_num(int x)
18
{
19
    int ans = 0;
20
    while (x)
21
    {
22
        if (x & 1)
23
            ans++;
24
        x >>= 1;
25
    }
26
    return ans;
27
}
28
int main()
29
{
30
    //freopen("proj.in", "r", stdin);
31
    //freopen("proj.out", "w", stdout);
32
    scanf("%d%d", &n, &m);
33
    for (int i = 1; i <= n; i++)
34
        for (int j = 1; j <= m; j++)
35
            scanf("%d", &a[i][j]);
36
    memset(F, 0x3f, sizeof(F));
37
    N = (1 << m) - 1;
38
    for (int i = 0; i <= N; i++)
39
    {
40
        //if ((((i >> 1) | (i << 1) | i) & N) == N)
41
        //{
42
            int ans = check(1, i);
43
            F[1][0][i] = ans;
44
            G[1][0][i] = Get_num(i);
45
        //}
46
    }
47
    for (int i = 1; i <= n; i++)
48
        for (int j = 0; j <= N; j++)
49
            for (int k = 0; k <= N; k++)
50
                for (int m = 0; m <= N; m++)
51
                    if (((j | k | m | (k << 1) | (k >> 1)) & (N)) == N)
52
                    {
53
                        if (F[i][j][k] + check(i + 1, m) < F[i + 1][k][m])
54
                        {
55
                            F[i + 1][k][m] = F[i][j][k] + check(i + 1, m);
56
                            G[i + 1][k][m] = G[i][j][k] + Get_num(m);
57
                        }
58
                    }
59
    int ans = 0x3f3f3f4f, num = 0;
60
    for (int i = 0; i <= N; i++)
61
    {
62
        if (F[n + 1][i][0] < ans)
63
        {
64
            ans = F[n + 1][i][0];
65
            num = G[n + 1][i][0];
66
        }
67
        else if (F[n + 1][i][0] == ans)
68
        {
69
            if (num > G[n + 1][i][0])
70
                num = G[n + 1][i][0];
71
        }
72
    }
73
    printf("%d %d", num, ans);
74
    //while (1)
75
    ;
76
}