[41] (CSP 集训) CSP-S 模拟 9

佚名 / 2024-10-08 / 原文

A.邻面合并

观察到 $m$ 很小,支持我们 $mn2^{2m}$

状压枚举二进制状态, $f_{i,j,k}$ 表示到第 $i$ 位的状态为 $j$,上一位状态为 $j$ ($i,j$ 为状压位) 的方案数

考虑转移的时候加了什么

判断这一行与上一行的联通情况,如果这一行的某一个连通块和上一行正好对上了,那么就可以直接扩展矩形,答案不增加,否则对每个连通块,答案加一

我对这个联通情况的设计是不咋好的,还是说一下

设 $a$ 是原矩阵第 $i$ 行,$b$ 是枚举到的状压状态，我判断连通块是根据

连通块内不存在 $a_j=0$ 的 $j$
连通块内不存在 $b_j=0$ 的 $j$

这么一做就会出很多冗余状态，但是我也不太会设计更好的了，所以就只能这样了

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[101][9];
int f[2][(1<<8)+1][(1<<8)+1];
int minn[101][(1<<8)+1];
vector<pair<int,int>>thi,las;
inline void work(int i,int j,vector<pair<int,int>>&ts){
    if(i==0) return;
    ts.clear();
    for(int k=1;k<=m;++k){
        int tmp=(j>>(k-1))&1;
        int tmplast=(k==1?tmp:(j>>(k-2))&1);
        if(a[i][k]==0){
            if(!ts.empty() and ts.back().second==0){
                ts.back().second=k-1;
            }
        }
        else if(k==1 or tmp!=tmplast or a[i][k-1]==0){
            if(!ts.empty() and ts.back().second==0){
                ts.back().second=k-1;
            }
            ts.push_back({k,0});
        }
    }
    if(!ts.empty() and ts.back().second==0){
        ts.back().second=m;
    }
}
int main(){
    freopen("merging.in","r",stdin);
    freopen("merging.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(minn,0x3f,sizeof minn);
    memset(minn[0],0,sizeof minn[0]);
    for(int i=1;i<=n;++i){
        memset(f[i&1],0x3f,sizeof f[i&1]);
        for(int j=0;j<=(1<<m)-1;++j){
            for(int k=0;k<=(1<<m)-1;++k){
                work(i,j,thi);
                work(i-1,k,las);
                int res=0;
                for(auto p:thi){
                    res++;
                    for(auto q:las){
                        if(p==q){
                            res--;
                            break;
                        }
                    }
                }
                f[i&1][j][k]=min(f[i&1][j][k],minn[i-1][k]+res);
                minn[i][j]=min(minn[i][j],f[i&1][j][k]);
            }
        }
    }
    int ans=0x7fffffff;
    for(int j=0;j<=(1<<m)-1;++j){
        ans=min(ans,minn[n][j]);
    }
    cout<<ans<<'\n';
}