博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ 2331 地板(插头DP)
阅读量:5931 次
发布时间:2019-06-19

本文共 2489 字,大约阅读时间需要 8 分钟。

题目链接:

题意:给出一个n*m的地面。有些是障碍。用L型的地板砖铺满。有多少种方案。

思路:用0表示没有插头,用1表示有插头且可以拐弯,用3表示有插头但是不能再拐弯了。

设有m列,轮廓线为[0,m]。对于格子(i,j),设左插头x上插头y,那么转移有:

(1)x=0,y=0:此时如图1-0,有三种转移,分别是1-1,1-2,1-3;

(2)x!=0,y!=0:此时只有当x=y=1时可以转移,就是合并插头,如图3-0;

(3)x和y中只有一个不是0。不妨设y=0,x!=0,那次此时若x=3,可以延续或者停止;若x=1,可以合并或者可以拐弯。

 

struct node{    int st[N],cnt[N],size;    int head[HashSize],next[N];        void init()    {        size=0;        clr(head,-1);    }        void add(int S,int x)    {        int t=S%HashSize;        int i;        for(i=head[t];i!=-1;i=next[i])        {            if(st[i]==S)            {                cnt[i]=(cnt[i]+x)%mod;                return;            }        }        st[size]=S;        cnt[size]=x;        next[size]=head[t];        head[t]=size++;    }};node f[2];int pre,cur;int n,m;char s[105][105];void init(){    RD(n,m);    int i,j;    FOR1(i,n) RD(s[i]+1);    char s1[105][105];    if(m>n)    {        FOR1(j,m) FOR1(i,n) s1[j][i]=s[i][j];        swap(n,m);        FOR1(i,n) FOR1(j,m) s[i][j]=s1[i][j];    }}int getBit(int st,int k){    return (st>>(k+k))&3;}int set0(int st,int k){    return st&(~(3<<(k+k)));}int set1(int st,int k){    st=set0(st,k);    return st|(1<<(k+k));}int set3(int st,int k){    return st|(3<<(k+k));}void add(int S,int x){    f[cur].add(S,x);}void DP(int i,int j){    int k,x,y,S,cnt;    FOR0(k,f[pre].size)    {        S=f[pre].st[k];        cnt=f[pre].cnt[k];        if(j==1)        {            if(getBit(S,m)) continue;            S=S<<2;        }        x=getBit(S,j-1);        y=getBit(S,j);        S=set0(S,j-1);        S=set0(S,j);        if(s[i][j]=='*')        {            if(x||y) continue;            add(S,cnt);            continue;        }        if(!x&&!y)        {            add(set1(S,j),cnt);            add(set1(S,j-1),cnt);            S=set3(S,j-1);            S=set3(S,j);            add(S,cnt);        }        else if(x&&y)        {            if(x==1&&y==1) add(S,cnt);        }        else if(x||y)        {            if(x==3) add(set3(S,j),cnt),add(S,cnt);            else if(x==1) add(set1(S,j),cnt),add(set3(S,j-1),cnt);                        if(y==3) add(set3(S,j-1),cnt),add(S,cnt);            else if(y==1) add(set1(S,j-1),cnt),add(set3(S,j),cnt);        }    }}int main(){    init();    pre=0; cur=1;    f[pre].init(); f[pre].add(0,1);    int i,j;    FOR1(i,n) FOR1(j,m)    {        f[cur].init();        DP(i,j);        swap(pre,cur);    }    int ans=0;    FOR0(i,f[pre].size) if(f[pre].st[i]==0) ans=f[pre].cnt[i];    PR(ans);}

 

 

 

转载地址:http://luutx.baihongyu.com/

你可能感兴趣的文章
L-1-17 Linux命令之压缩与归档命令
查看>>
Eclipse_java_log4j学习记录
查看>>
lvs haproxy lvs三种软负载均衡的比较
查看>>
Elasticsearch 索引、更新、删除文档
查看>>
使用yum安装MariaDB
查看>>
python字典的提取
查看>>
在Spring中整合JUnit单元测试
查看>>
【C#】xml序列化及反序列化
查看>>
oracle外连接,Oracle中Left Outer Join和外关联(+)的区别
查看>>
Django运维后台的搭建之一:使用model建立数据信息
查看>>
VM 虚拟机上 CentOS7 永久修改系统时间
查看>>
关于LP Wizard生成Allegro封装无焊盘的解决方案
查看>>
php日期时间计算,转载
查看>>
php 排查函数文件执行路径的打印
查看>>
批量上传图片
查看>>
linux必需掌握的基础(二)
查看>>
回归自然-测试、回归、预发布、灰度发布、生产环境自己的理解
查看>>
Java 线程详解(二)synchronize
查看>>
我的友情链接
查看>>
常用的脚本编程知识点
查看>>