标签：插头 Set cur int state DP && 模板
- 为了利用位运算的良好性质，采用四进制状态压缩代替三进制
- 通过哈希表压缩有限的状态
- 与普通的按行滚动的滚动数组不同，插头DP中的滚动数组是按格滚动的
- 因为布尔数组值默认为false，所以我们可以用“true”代表“可通行”
- 转移时需要找到与之匹配的括号——实现算法时不能够总是代入理想模型
点击查看代码
//轮廓线DP
#include <bits/stdc++.h>
using namespace std;
const int M=100007;
long long f[2][100105];
int h[2][100105];
bool g[15][15];
int ei,ej,n,m;
bool opt;
queue<int>q[2];
int find(int cur,int state)
{
int t=state%M;
while(h[cur][t]!=-1&&h[cur][t]!=state)
{
t++;
if(t==M)
{
t=0;
}
}
return t;
}
int get(int state,int k)
{
return (state>>(k*2))&3;
}
int Set(int k,int va)
{
return va*(1<<(2*k));
}
void insert(int cur,int state,long long w)
{
if(opt==true)
{
state=(state<<2);
}
int t=find(cur,state);
if(h[cur][t]==-1)
{
h[cur][t]=state;
q[cur].push(t);
}
f[cur][t]+=w;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
char c;
cin>>c;
if(c=='.')
{
g[i][j]=true;
ei=i;
ej=j;
}
}
}
memset(h,-1,sizeof(h));
insert(0,0,1);
long long ans=0;
int cur=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
opt=(j==m);
memset(h[cur],-1,sizeof(h[cur]));
memset(f[cur],0,sizeof(f[cur]));
cur=cur^1;
while(!q[cur].empty())
{
int t=q[cur].front(),state=h[cur][t];
int x=get(state,j-1),y=get(state,j);
q[cur].pop();
if(g[i][j]==false)
{
if(x==0&&y==0)
{
insert(cur^1,state,f[cur][t]);
}
}
else
{
if(x==0&&y==0)
{
if(g[i][j+1]&&g[i+1][j])
{
insert(cur^1,state+Set(j-1,1)+Set(j,2),f[cur][t]);
}
}
else if(x==0)
{
if(g[i][j+1])
{
insert(cur^1,state,f[cur][t]);
}
if(g[i+1][j])
{
insert(cur^1,state+Set(j-1,y)-Set(j,y),f[cur][t]);
}
}
else if(y==0)
{
if(g[i+1][j])
{
insert(cur^1,state,f[cur][t]);
}
if(g[i][j+1])
{
insert(cur^1,state+Set(j,x)-Set(j-1,x),f[cur][t]);
}
}
else if(x==y)
{
int s=1;
if(x==1)
{
for(int k=j+1;k<=m;k++)
{
if(get(state,k)==1)
{
s++;
}
else if(get(state,k)==2)
{
s--;
if(s==0)
{
insert(cur^1,state-Set(j-1,x)-Set(j,y)-Set(k,1),f[cur][t]);
break;
}
}
}
}
else if(x==2)
{
for(int k=j-2;k>=0;k--)
{
if(get(state,k)==1)
{
s--;
if(s==0)
{
insert(cur^1,state-Set(j-1,x)-Set(j,y)+Set(k,1),f[cur][t]);
break;
}
}
else if(get(state,k)==2)
{
s++;
}
}
}
}
else
{
if(x==1&&y==2)
{
if(i==ei&&j==ej)
{
ans+=f[cur][t];
}
}
else if(x==2&&y==1)
{
insert(cur^1,state-Set(j-1,x)-Set(j,y),f[cur][t]);
}
}
}
}
}
}
cout<<ans<<endl;
return 0;
}
标签：插头,
Set,
cur,
int,
state,
DP,
&&,
模板
From： https://www.cnblogs.com/watersail/p/18306321