题目描述
莫莉斯·乔是圣域里一个叱咤风云的人物，他凭借着自身超强的经济头脑，牢牢控制了圣域的石油市场。
圣域的地图可以看成是一个n*m的矩阵。每个整数坐标点(x , y)表示一座城市 （ 1 ≤ x ≤ n , 1 ≤ y ≤ m ） （ 1\le x\le n,1\le y\le m） （1≤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 × m ≤ 50 且 m ≤ n ) ( n \times m \le 50 且 m\le n) (n×m≤50且m≤n)，表示矩阵的大小。
接下来一个n行m列的矩阵F， F i , j F_{i, j} Fi,j 表示在城市(i,j)建造油库的代价。
输出格式： 输出两个数，建造方案的油库个数和方案的总代价。
其中数据范围是
对于30%数据满足 n × m ≤ 25 n \times m \le 25 n×m≤25 ;
对于100%数据满足 n × m ≤ 50 , 0 ≤ F i , j ≤ 100000 n \times m \le 50,0 \le F_{i, j} \le100000 n×m≤50,0≤Fi,j≤100000
看一下这个数据范围，不难得出，m<=7
所以可以直接进行dp
首先我们先预处理一下cost[i][j]表示在第i行，建造j这个状态的油库需要的最小代价是多少
num[j]是j这个状态有几个油库（也就是有几个一） 可以直接用_builtin_popcount()来算
QAQ然后考虑dp
因为第i行的状态只能转移到i+1的状态转移过来
所以f[i][j][k]表示前i-1行的已经都能够合法，第i行的状态是j，第i-1行的状态时k的最小花费
同时g[i][j][k]则表示对应状态的油库数量
首先我们考虑转移条件~~
因为是要求前i行的状态合法，才能转移到i+1
所以要求 ( p ∣ j ∣ k ∣ j < < 1 ∣ j > > 1 ) & 2 m − 1 = = 2 m − 1 (p| j | k|{j << 1} |{j >> 1}) \&{2^m-1}\ ==\ {2^m -1} (p∣j∣k∣j<<1∣j>>1)&2m−1 == 2m−1 这个条件也就是对应的是第i行是所有的位置都是合法的
然后考虑对于 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]能转移到哪个状态
我们在转移的时候，枚举j,k,p 则 f [ i + 1 ] [ p ] [ j ] = f [ i ] [ j ] [ k ] + c o s t [ i + 1 ] [ p ] f[i+1][p][j]=f[i][j][k]+cost[i+1][p] f[i+1][p][j]=f[i][j][k]+cost[i+1][p] g [ i + 1 ] [ p ] [ j ] = g [ i ] [ j ] [ k ] + n u m [ p ] g[i+1][p][j]=g[i][j][k]+num[p] g[i+1][p][j]=g[i][j][k]+num[p]
同时当上述的f在转移时相等的时的时候，我们也可以考虑更新g 不懂的可以看一下代码
if (((j|k|p|(j<<1)|(j>>1))&((1 << m)-1))==((1 << m)-1)) { if (f[i][j][k]+sum[i+1][p]<f[i+1][p][j]) { f[i+1][p][j]=f[i][j][k]+sum[i+1][p]; g[i+1][p][j]=g[i][j][k]+num[p]; } else { if (f[i][j][k]+sum[i+1][p]==f[i+1][p][j]) { g[i+1][p][j]=min(g[i+1][p][j],g[i][j][k]+num[p]); }QWQ最后的答案就是 f[n+1][0][i] 以及对应最小费用的最小油库个数
上代码
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<cstdlib> #include<queue> #include<map> #include<vector> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } const int maxn = 210; int a[61][61]; int f[61][maxn][maxn]; int g[61][maxn][maxn]; int sum[61][maxn]; int n,m; int num[maxn]; int ans1=1e9; int ans2=1e9; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) a[i][j]=read(); for (int i=1;i<=n;i++) { for (int j=0;j<(1 << m);j++) { for (int k=1;k<=m;k++) { if (j&(1 << (k-1))) { sum[i][j]+=a[i][k]; } } } } memset(f,127/3,sizeof(f)); memset(g,127/3,sizeof(g)); for (int j=0;j<(1 << m);j++) num[j]=__builtin_popcount(j); for (int i=0;i<(1 << m);i++) { f[1][i][0]=sum[1][i]; g[1][i][0]=num[i]; } for (int i=1;i<=n;i++) { for (int j=0;j<(1 << m);j++) for (int k=0;k<(1 << m);k++) { for (int p=0;p<(1 << m);p++) { if (((j|k|p|(j<<1)|(j>>1))&((1 << m)-1))==((1 << m)-1)) { if (f[i][j][k]+sum[i+1][p]<f[i+1][p][j]) { f[i+1][p][j]=f[i][j][k]+sum[i+1][p]; g[i+1][p][j]=g[i][j][k]+num[p]; } else { if (f[i][j][k]+sum[i+1][p]==f[i+1][p][j]) { g[i+1][p][j]=min(g[i+1][p][j],g[i][j][k]+num[p]); } } } } } } for (int i=0;i<(1 << m);i++) { if (ans1>f[n+1][0][i]) { ans1=f[n+1][0][i]; ans2=g[n+1][0][i]; } else { if (ans1==f[n+1][0][i]) ans2=min(ans2,g[n+1][0][i]); } } cout<<ans2<<" "<<ans1; return 0; }这大概是QWQ第一篇makedown的博客 嗯
