关灯问题II 状压DP

\(n\)个灯，\(m\)个按钮，每个按钮都会对每个灯有不同影响，问最少多少次使灯熄完。

\(n\le 10,m\le 100\)

状压DP的好题，体现了状压的基本套路与二进制操作

注意到此题\(n\)极小，一般小于\(16\)就可以做状压，并且发现每次转移时需要每盏灯的信息，于是我们直接将灯状态塞进二进制即可。

首先我们从初态开始按顺序枚举状态，然后枚举每次状态的决策，最后按题意转移到下一个状态即可。

#include <cstdio>

#include <algorithm>

#include <cstring>

#define MAXN 11

#define MAXM 110

using namespace std;

int n,m;

int a[MAXM][MAXN];

int f[1<<10];

int main(){

    scanf("%d%d", &n, &m);

    int mxf=(1<<n)-1;

    for(int i=1;i<=m;++i)

        for(int j=1;j<=n;++j)

            scanf("%d", &a[i][j]);

    memset(f, 0x3f, sizeof f);

    f[mxf]=0;

    for(int i=mxf;i>=0;--i){

        for(int j=1;j<=m;++j){

            int to=i;

            for(int k=1;k<=n;++k){

                if(a[j][k]==0) continue;

                if(a[j][k]==1 && (to & (1<<(k-1))) ) to=to^(1<<(k-1));

                if(a[j][k]==-1 && !(to & (1<<(k-1))) ) to=to^(1<<(k-1));

            }

            f[to]=min(f[i]+1, f[to]);

        }

    }

    if(f[0]==0x3f3f3f3f) puts("-1");

    else printf("%d\n", f[0]);

    return 0;

}

巴特西

关灯问题II 状压DP

关灯问题II 状压DP

最新文章

热门文章