题目描述
莫莉斯·乔是圣域里一个叱咤风云的人物，他凭借着自身超强的经济头脑，牢牢控制了圣域的石油市场。
圣域的地图可以看成是一个n*m的矩阵。每个整数坐标点(x , y)表示一座城市吗，两座城市间相邻的定义为：对于城市(Ax, Ay)和城市(Bx, By)，满足 \((Ax-Bx)^2 + (Ay-By)^2=1\)
由于圣域的石油贸易总量很大，莫莉斯意识到不能让每笔石油订购单都从同一个油库里发货。为了提高效率，莫莉斯·乔决定在其中一些城市里建造油库，最终使得每一个城市X都满足下列条件之一：
1.该城市X内建有油库，
2.某城市Y内建有油库，且城市X与城市Y相邻。
与地球类似，圣域里不同城市间的地价可能也会有所不同，所以莫莉斯想让完成目标的总花费尽可能少。如果存在多组方案，为了方便管理，莫莉斯会选择建造较少的油库个数。
输入输出格式
输入格式：
第一行两个正整数n,m，表示矩阵的大小。
接下来一个n行m列的矩阵F,\(F[i][j]\) 表示在城市(i,j)建造油库的代价。
输出格式：
输出两个数，建造方案的油库个数和方案的总代价。
输入输出样例
输入样例#1：
输出样例#1：
说明
对于30%数据满足 \(n*m<=25\) ;
对于100%数据满足\(n*m<=50,F[i][j]<=100000\)
好像挺水的一道状压
然而我还是WA了一发
感觉自己DP水平是普及==
一看数据范围，显然状压
但是我们发现对该点有贡献的点是该点的上下左右四个点
所以我们就设\(f[i][j][k][0]\)表示在第i行的状态是j，第i-1行的状态是k的最小花费
\(f[i][j][k][1]\)表示的是在最小花费下的最小建筑数量
如果这一层，上一层和上上层的状态可以满足上一层的状态就转移
最后统计一下第n行的合法答案就好辣
#include<cstdio>
#include<cstring>
#include<algorithm>
const int M = 55 ;
const int N = 130 ;
const int INF = 1e9 ;
using namespace std ;
inline int read() {
char c = getchar() ; int x = 0 , w = 1 ;
while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
return x*w ;
}
int n , m ;
int f[M][N][N][2] ;
// f[i][j][k] 第i-1行的状态是j，第i行的状态是k
int val[M][M] , MinC = INF , MinNum = INF ;
inline bool Istrue(int sit1 , int sit2 , int sit3) {
int sit = ((sit1|sit2)|sit3) ;
for(int i = 1 ; i <= m ; i ++) {
if(sit & (1<<(i - 1))) continue ;
if((sit2 & (1<<(i - 2)))|(sit2 & (1<<i))) continue ;
return false ;
}
return true ;
}
inline int query(int x , int sit , int &Num) {
int temp = 0 ;
for(int i = 1 ; i <= m ; i ++)
if(sit & (1<<(i - 1)))
temp += val[x][i] , ++ Num ;
return temp ;
}
int main() {
n = read() ; m = read() ;
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++)
val[i][j] = read() ;
for(int i = 0 ; i <= n ; i ++)
for(int j = 0 ; j < (1<<m) ; j ++)
for(int k = 0 ; k < (1<<m) ; k ++)
f[i][j][k][0] = f[i][j][k][1] = INF ;
int Num = 0 ;
for(int i = 0 ; i < (1<<m) ; i ++) {
Num = 0 ;
f[1][i][0][0] = query(1 , i , Num) ;
f[1][i][0][1] = Num ;
}
for(int i = 2 ; i <= n ; i ++) {
for(int j = 0 ; j < (1<<m) ; j ++) { // 本层
for(int k = 0 ; k < (1<<m) ; k ++) { // 上一层
for(int l = 0 ; l < (1<<m) ; l ++) { // 上上层
Num = 0 ;
if(!Istrue(j , k , l)) continue ;
int temp = f[i - 1][k][l][0] + query(i , j , Num) ;
if(f[i][j][k][0] > temp) {
f[i][j][k][0] = temp ;
f[i][j][k][1] = f[i - 1][k][l][1] + Num ;
}
else if(f[i][j][k][0] == temp && f[i][j][k][1] > f[i - 1][k][l][1] + Num)
f[i][j][k][1] = f[i - 1][k][l][1] + Num ;
}
}
}
}
for(int i = 0 ; i < (1<<m) ; i ++)
for(int j = 0 ; j < (1<<m) ; j ++) {
if(!Istrue(j , i , 0)) continue ;
if(f[n][i][j][0] < MinC) {
MinC = f[n][i][j][0] ;
MinNum = f[n][i][j][1] ;
}
else if(f[n][i][j][0] == MinC && f[n][i][j][1] < MinNum)
MinNum = f[n][i][j][1] ;
}
printf("%d %d\n",MinNum , MinC) ;
return 0 ;
}