对插头 DP 的理解还不是很透彻.
先说一下肤浅的理解吧.
插头 DP 使用范围: 指数级复杂度, 且适用于解决网格图连通性问题, 如哈密顿回路等问题. 插头一般指每相邻 2 个网格的接口.
题目难度: 一般不可做.
使用三进制状态, 用 0 表示没有插头, 1 表示左括号插头, 2 表示右括号插头, 而由于位运算常数特别小, 可以采用四进制 + 手工 hash 的做法. 处理好状态与编号的对应关系后进行 dp, 复杂度就只与合法状态数有关了, 时间复杂度 O(snm^2), 其中 s 为合法状态数 (不超过 42000), 而第二维的 m 显然也是不满的, 因此可以通过本题.
状态转移详见代码 (因为没时间写了, 先咕着)
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N=3e5+7,mod=299989;
- int n,m,D,ex,ey,tot[2],mp[20][20],pw[20],hd[N],nxt[N],a[2][N];
- ll ans,f[2][N];
- char str[20];
- void add(int x,ll y)
- {
- int u=x%mod+1;
- for(int i=hd[u];i;i=nxt[i])if(a[D][i]==x){f[D][i]+=y;return;}
- nxt[++tot[D]]=hd[u],hd[u]=tot[D];
- a[D][tot[D]]=x,f[D][tot[D]]=y;
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)
- {
- scanf("%s",str+1);
- for(int j=1;j<=m;j++)
- if(str[j]=='.'){mp[i][j]=1,ex=i,ey=j;}
- }
- pw[0]=1;
- for(int i=1;i<=max(n,m);i++)pw[i]=pw[i-1]*4;
- a[0][1]=0,tot[0]=f[0][1]=1;
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=tot[D];j++)a[D][j]*=4;
- for(int j=1;j<=m;j++)
- {
- memset(hd,0,sizeof hd);
- tot[D^=1]=0;
- for(int k=1;k<=tot[D^1];k++)
- {
- int S=a[D^1][k],b1=(S>>(j*2-2))%4,b2=(S>>(j*2))%4;
- ll p=f[D^1][k];
- if(!mp[i][j])
- {
- if(!b1&&!b2)add(S,p);
- }
- else if(!b1&&!b2)
- {
- if(mp[i+1][j]&&mp[i][j+1])add(S+pw[j-1]+2*pw[j],p);
- }
- else if(!b1&&b2)
- {
- if(mp[i][j+1])add(S,p);
- if(mp[i+1][j])add(S-b2*pw[j]+b2*pw[j-1],p);
- }
- else if(b1&&!b2)
- {
- if(mp[i+1][j])add(S,p);
- if(mp[i][j+1])add(S-b1*pw[j-1]+b1*pw[j],p);
- }
- else if(b1==b2)
- {
- if(b1==1)
- {
- int tmp=1;
- for(int l=j+1;l<=m;l++)
- {
- if((S>>(l*2))%4==1)tmp++;
- if((S>>(l*2))%4==2)tmp--;
- if(!tmp){add(S-pw[l]-pw[j-1]-pw[j],p);break;}
- }
- }
- if(b1==2)
- {
- int tmp=1;
- for(int l=j-2;l>=0;l--)
- {
- if((S>>(l*2))%4==1)tmp--;
- if((S>>(l*2))%4==2)tmp++;
- if(!tmp){add(S+pw[l]-2*pw[j-1]-2*pw[j],p);break;}
- }
- }
- }
- else if(b1==2&&b2==1)add(S-2*pw[j-1]-pw[j],p);
- else if(i==ex&&j==ey)ans+=p;
- }
- }
- }
- printf("%lld",ans);
- }
- View Code
来源: http://www.bubuko.com/infodetail-3035974.html