BZOJ 3934 CQOI 2015 标识设计插头DP

本文主要是介绍BZOJ 3934 CQOI 2015 标识设计插头DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面：http://www.lydsy.com/JudgeOnline/problem.php?id=3934

很容易想到插头DP。显然只需要记录插头是否存在，而不需要记录插头的连通性。

把一个L看做是“一个只含下插头的格子——它下面的若干（可以为零）个含上下插头的格子——含一个上插头、一个右插头的格子——它右边的若干（可以为零）个含左右插头的格子——它右边一个含一个左插头的格子”这五部分构成。

根据题意，每个格子至多含有两个插头，且在含有两个插头的情况下只有三种是合法的。逐格递推时，注意判断一下。

需要记录当前状态已经含有几个“L”的开头——只含下插头的格子。同时为了统计答案，还要记录已经有几个”L”已经结束——填完了几个只含左插头的格子。这两个东西可以分别用2个二进制位记录。

当已经填了3个只含下插头的格子、2个只含左插头的格子，且当前决策格可以是一个只含左插头的格子时，更新答案。

各种状态的转移都比较简单。

#include<stdio.h>
#include<algorithm>
#include<cstring>
#define ll long long
#define MAXM 666666
#define Mod 23333
using namespace std;int N,M,Map[35][35];
char s[35][35];
ll Ans;int las[Mod],nex[MAXM],en[MAXM],tot;
void Add(int x,int y){en[++tot]=y;nex[tot]=las[x];las[x]=tot;
}int cur,pre,total[2],En;
ll f[2][MAXM],state[2][MAXM];void Ins(ll st,ll val){int p=st%Mod,i;for(i=las[p];i;i=nex[i])if(st==state[cur][en[i]]){f[cur][en[i]]+=val;return;}total[cur]++;state[cur][total[cur]]=st;f[cur][total[cur]]=val;Add(p,total[cur]);
}ll Ec(ll st,int p,int q){return ((st<<4)|(p<<2)|q);
}void PlugDP(){int i,j,k,d,r,p,q;ll st,tmp;cur=0;pre=1;    total[0]=1;state[0][1]=0;f[0][1]=1;En=(1<<M+1)-1;for(i=1;i<=N;i++){for(j=1;j<=total[cur];j++)state[cur][j]=(state[cur][j]&15)|(state[cur][j]>>4<<5);for(j=1;j<=M;j++){cur^=1;pre^=1;total[cur]=0;memset(las,0,sizeof(las));tot=0;for(k=1;k<=total[pre];k++){st=state[pre][k]>>4;tmp=f[pre][k];r=st>>j-1&1;d=st>>j&1;q=state[pre][k]&3;p=(state[pre][k]&15)>>2;if(r&&d)continue;else if(!Map[i][j]){if(!r&&!d)Ins(Ec(st,p,q),tmp);}else {if(!r&&!d){Ins(Ec(st,p,q),tmp);if(p<3&&Map[i+1][j])Ins(Ec(st|(1<<j-1),p+1,q),tmp);}else if(!r&&d){if(Map[i][j+1])Ins(Ec(st,p,q),tmp);if(Map[i+1][j])Ins(Ec(st^(1<<j-1)^(1<<j),p,q),tmp);}else {if(Map[i][j+1])Ins(Ec(st^(1<<j-1)^(1<<j),p,q),tmp);if(p==3&&q==2)Ans+=tmp;else Ins(Ec(st^(1<<j-1),p,q+1),tmp);}}}}}
}int main(){int i,j;scanf("%d%d",&N,&M);for(i=1;i<=N;i++)scanf("%s",&s[i][1]);for(i=1;i<=N;i++)for(j=1;j<=M;j++)if(s[i][j]=='.')Map[i][j]=1;PlugDP();printf("%lld\n",Ans);
}