P1539题解

real60t · 2021-09-16 20:59:49 · 题解

P1539题解

1.分析

数据范围: n\times m\le225。

则 \min(m,n)\le15。我们可以将较小值作为的列数，再对每一行进行状压，用 c 数组储存每行方案，dp 求解。

我们算一下时间复杂度，由于相邻不能同时为 1，所以很多情况都被舍掉，所以当 m=15 时，每一行只有 1597 种情况，不会超时。

但题目给出的矩阵有些数已经填好，无法改变，这怎么处理呢？

设 s_i 为第 i 行已填数字 1 的分布情况，t_i 为第 i 行已填数字 0 的分布情况。如果第 i 行中方案 c_k 满足 (t_i\;and\;c_k)=t_i 且 s_i\;and\;(not\;c_k)=s_i，则方案 k 不与已填数字冲突。

最后的 dp 就比较简单了，设 f[i][j] 为第 i 行使用第 j 种方案的方法数，d 每行合法方案种数。

状态转移方程：f[i][j]=\sum\limits_{k=1}^df[i-1][k](c[j]\;and\;c[k]=0)。

最终答案：ans=\sum\limits_{i=1}^df[n][i]。

初始化：f[0][1]=0。

时间复杂度：\mathcal O(nd^2)。

2.Code

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int mod=10007;
int n,m=15,ans,t[230],s[230],c[1600],f[230][1600];
char a[230][230],b[230][230];
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
    //如果n<m,将矩阵顺时针旋转90度,以保证列数m<=15 
    if(n<m) {
        swap(n,m);
        memcpy(b,a,sizeof(b));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)a[i][j]=b[m-j+1][i];       
    }
    //预处理s,t数组 
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(a[i][j]=='1')s[i]+=1<<m-j;
            if(a[i][j]=='0')t[i]+=1<<m-j;
        }
    }   
    //预处理每行方案,存入数组c 
    for(int i=0;i<1<<m;i++) 
        if(!(i>>1&i))c[++c[0]]=i;
    f[0][1]=1;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=c[0];j++) {
            //判断方案是否合法 
            if((s[i]&c[j])!=s[i])continue;
            if((t[i]&(~c[j]))!=t[i])continue;
            for(int k=1;k<=c[0];k++) 
                if(!(c[j]&c[k]))f[i][j]=(f[i][j]+f[i-1][k])%mod;
        }
    }
    for(int i=1;i<=c[0];i++)ans=(ans+f[n][i])%mod;
    printf("%d",ans);
    return 0;
}