本题是一道十分好的状压dp练手题

基本思路

初看这道题时其实并没有什么思路，在看到\(n\le 10\)时才想到使用状压dp
有时候搜索时间复杂度很高，也没有方法优化到多项式复杂度，依然可以利用题目中的子问题重叠性得到不错的算法
一个比较显然的事实是：一个按钮不会按多次。所以总的次数不超过\(m\)，于是我们写出状态定义：
一个状态为\(n\)位二进制数，其中\(1\)表示打开，\(0\)表示闭合
设\(f(i)\)为达到\(i\)的状态的最小步数
在列出状态转移方程时遇到了麻烦，对于\(0\)的操作，无法得知是从哪个状态转移而来，但是顺推很方便，所以使用向前递推法

代码

#include <bits/stdc++.h>

using namespace std;
const int N=10,M=1e2+5,INF=0x3f3f3f3f;

int n,m,a[M][N];
int f[1<<N]; 

int change(int p,int j) {
	for(int i=0;i<=n-1;i++) {
		if(a[j][i]==-1) p|=1<<i;
		if(a[j][i]==1) if(p>>i&1) p^=1<<i;
	}
	return p;
}

int main() {
	memset(f,0x3f,sizeof(f));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	  for(int j=0;j<=n-1;j++)
	    scanf("%d",&a[i][j]);
	int bound=(1<<n)-1;
	f[bound]=0;	//初始状态为全1
	for(int i=0;i<=m-1;i++) {
		for(int j=0;j<=bound;j++) {
			if(f[j]==INF) continue;	//小优化
			for(int k=1;k<=m;k++) {
				int l=change(j,k);
				f[l]=min(f[l],1+f[j]);	//向前递推
			}
		}
	}
	if(f[0]==INF) printf("-1");
	else printf("%d",f[0]);
	return 0;
}