问题描述
莫莉斯·乔是圣域里一个叱咤风云的人物,他凭借着自身超强的经济头脑,牢牢控制了圣域的石油市场。
圣域的地图可以看成是一个n*m的矩阵。每个整数坐标点(x , y)表示一座城市(1<=x<= n, 1<=y<=m)。两座城市间相邻的定义为:对于城市和城市,满足。 由于圣域的石油贸易总量很大,莫莉斯意识到不能让每笔石油订购单都从同一个油库里发货。为了提高效率,莫莉斯·乔决定在其中一些城市里建造油库,最终使得每一个城市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) ;}