好学易懂 从零开始的插头DP

好学易懂 从零开始的插头DP（三）

写在前面

这篇文章主要是介绍一些括号表示法和简单回路的基本变化，下一篇会是一些非回路（最小表示），毒瘤状态（正wa着所以咕着），结合矩阵乘法加速等一些复杂应用。下下篇应该会是结尾，介绍一些除了路径问题以外的应用。这几篇题目的部分不会讲的非常详细，主要是自己思考，所以只会说大体思路。

FZU 1977（这个OJ要用I64d不能lld，不然wa）

题目大意：
n*m的格子，有些格子不能走，有些必须走，有些可以走。问，合法回路个数。
题目分析：
对于基本模板，有两个地方要处理。
一是插头转移，转移的时候不仅要考虑插头情况，还要考虑格点情况，这个题目格点情况有些变化。
二是终止格点不再确定。我的思路是最后一个必须走的点和它之后的可走的点都可以做终止格点，终止条件是只有一个左括号和右括号。
代码如下：

#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
const __int64 hs=10007;
__int64 n,m,ex,ey,now,last,ans;
__int64 a[13][13],b[13][13],head[100010],nex[100010],que[2][100010],val[2][100010],cnt[2],inc[13];
void init()
{
	scanf("%lld%lld",&n,&m);
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(head,0,sizeof(head));	
	memset(nex,0,sizeof(nex));	 
	memset(que,0,sizeof(que));
	memset(val,0,sizeof(val));
	memset(cnt,0,sizeof(cnt));
	memset(inc,0,sizeof(inc)); 
	ans=0;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			char ch=getchar();
			while (ch!='*'&&ch!='O'&&ch!='X') ch=getchar();
			if (ch=='X') a[i][j]=0;
			else if (ch=='*') a[i][j]=2;
			else 
			{
				a[i][j]=1;
				ex=i;
				ey=j;
			}
		}
	}
	inc[0]=1;
	for(int i=1;i<=13;i++)
	{
       inc[i]=inc[i-1]<<2;
	}
	for (int i=n;i>=1;i--)
	{
		for (int j=m;j>=1;j--)
		{
			if (a[i][j]!=0) b[i][j]=1;
			if (i==ex&&j==ey) return;
		}
	}
}
inline void insert(__int64 bit,__int64 num)
{
   __int64 u=bit%hs+1;
   for(int i=head[u];i;i=nex[i])
   {
       if(que[now][i]==bit)
	   {
           val[now][i]+=num;
           return;
       }
   }
   nex[++cnt[now]]=head[u];
   head[u]=cnt[now];
   que[now][cnt[now]]=bit;
   val[now][cnt[now]]=num;
}
inline void solve()
{
	cnt[now]=1; 
	val[now][1]=1; 
	que[now][1]=0;
	for(int i=1;i<=n;i++)
	{
    	for(int j=1;j<=cnt[now];j++)
    	{
        	que[now][j]<<=2;
    	}
       	for(int j=1;j<=m;++j)
	   	{
        	memset(head,0,sizeof(head));
        	last=now; now^=1;
           	cnt[now]=0;
        	for(int k=1;k<=cnt[last];++k)
			{
               	__int64 bit=que[last][k],num=val[last][k];
               	__int64 b1=(bit>>((j-1)*2))%4,b2=(bit>>(j*2))%4;
               	if(a[i][j]==0)
			   	{
                   if(!b1&&!b2) insert(bit,num);
               	}
			   	else if(!b1&&!b2)
				{
					if (a[i][j]==2) insert(bit,num);
                   	if(a[i+1][j]&&a[i][j+1]) insert(bit+inc[j-1]+inc[j]*2,num);
               	}
				else if(!b1&&b2)
				{
                   	if(a[i][j+1]) insert(bit,num);
                   	if(a[i+1][j]) insert(bit-inc[j]*b2+inc[j-1]*b2,num);
               	}
				else if(b1&&!b2)
				{
                   	if(a[i+1][j]) insert(bit,num);
                   	if(a[i][j+1]) insert(bit-inc[j-1]*b1+inc[j]*b1,num);
               	}
				else if(b1==1&&b2==1)
				{
                   	int flag=1;
                   	for(int l=j+1;l<=m;++l)
					{
                       	if((bit>>(l*2))%4==1) flag++;
                       	if((bit>>(l*2))%4==2) flag--;
                       	if(!flag)
						{
                           	insert(bit-inc[j]-inc[j-1]-inc[l],num);
                           	break;
                       	}
                   	}
               	}
				else if(b1==2&&b2==2)
				{
                   	int flag=1;
                   	for(int l=j-2;l>=0;--l)
				   	{
                       	if((bit>>(l*2))%4==1) flag--;
                       	if((bit>>(l*2))%4==2) flag++;
                       	if(!flag)
						{
                           	insert(bit-inc[j]*2-inc[j-1]*2+inc[l],num);
                           	break;
                       	}
                   	}
               	}
				else if(b1==2&&b2==1) insert(bit-inc[j-1]*2-inc[j],num);
					else if (bit-inc[j-1]-inc[j]-inc[j]==0&&b[i][j]==1) ans=ans+num;
           	}
       	}
   	}
}
int main()
{
	int t;
	scanf("%lld",&t);
	for (int i=1;i<=t;i++)
	{
		init();
		solve();
		printf("Case %d: %I64d\n",i,ans);
	}
	return 0;
}

P3190 [HNOI2007]神奇游乐园

题目大意：
n*m的格子（n<=100,m<=6)，每个格子有一个权值。求最大权回路的权值。
题目分析：
现在我们已经会处理可选格点了。这里全部都是可选格点。再加上一个很简单的变化，状态改为记录最大权。同时处理插头的时候判断要不要加上这个点的权值。
代码如下：

#include<cstdio>
#include<cstring>
using namespace std;
const long long hs=299987;
long long n,m,ex,ey,now,last,ans;
long long a[101][8],head[300000],next[2<<8],que[2][2<<8],val[2][2<<8],cnt[2],inc[10];
void init()
{
	scanf("%lld%lld",&n,&m);
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			scanf("%lld",&a[i][j]);
		}
	}
	inc[0]=1;
	for(int i=1;i<=8;i++)
	{
       inc[i]=inc[i-1]<<2;
	}
	ans=-(n*m*1001);
}
inline void insert(long long bit,long long num)
{
   long long u=bit%hs+1;
   for(int i=head[u];i;i=next[i])
   {
       if(que[now][i]==bit)
	   {
           if (val[now][i]<num) val[now][i]=num;
           return;
       }
   }
   next[++cnt[now]]=head[u];
   head[u]=cnt[now];
   que[now][cnt[now]]=bit;
   val[now][cnt[now]]=num;
}
inline void solve()
{
	cnt[now]=1; 
	val[now][1]=0; 
	que[now][1]=0;
	for(int i=1;i<=n;i++)
	{
    	for(int j=1;j<=cnt[now];j++)
    	{
        	que[now][j]<<=2;
    	}
       	for(int j=1;j<=m;++j)
	   	{
        	memset(head,0,sizeof(head));
        	last=now; now^=1;
           	cnt[now]=0;
        	for(int k=1;k<=cnt[last];++k)
			{
               	long long bit=que[last][k],num=val[last][k]+a[i][j];
               	long long b1=(bit>>((j-1)*2))%4,b2=(bit>>(j*2))%4;
			   	if(!b1&&!b2)
				{
					insert(bit,num-a[i][j]);
                   	if(i!=n&&j!=m) insert(bit+inc[j-1]+inc[j]*2,num);
               	}
				else if(!b1&&b2)
				{
                   	if(j!=m) insert(bit,num);
                   	if(i!=n) insert(bit-inc[j]*b2+inc[j-1]*b2,num);
               	}
				else if(b1&&!b2)
				{
                   	if(i!=n) insert(bit,num);
                   	if(j!=m) insert(bit-inc[j-1]*b1+inc[j]*b1,num);
               	}
				else if(b1==1&&b2==1)
				{
                   	int flag=1;
                   	for(int l=j+1;l<=m;++l)
					{
                       	if((bit>>(l*2))%4==1) flag++;
                       	if((bit>>(l*2))%4==2) flag--;
                       	if(!flag)
						{
                           	insert(bit-inc[j]-inc[j-1]-inc[l],num);
                           	break;
                       	}
                   	}
               	}
				else if(b1==2&&b2==2)
				{
                   	int flag=1;
                   	for(int l=j-2;l>=0;--l)
				   	{
                       	if((bit>>(l*2))%4==1) flag--;
                       	if((bit>>(l*2))%4==2) flag++;
                       	if(!flag)
						{
                           	insert(bit-inc[j]*2-inc[j-1]*2+inc[l],num);
                           	break;
                       	}
                   	}
               	}
				else if(b1==2&&b2==1) insert(bit-inc[j-1]*2-inc[j],num);
					else if (num>ans) ans=num;
           	}
       	}
   	}
}
int main()
{
   init();
   solve();
   printf("%lld\n",ans);
   return 0;
}

hdu 1964

题目大意：
每个相邻格子之间有一个墙，走过需要花费一定的代价，现在求经过所有点的闭合回路的最小代价。
题目分析：
通过上一题，我们学会了求最大值，最小值同理。这里的代价不在格点上在插头上，稍微转换下就行了。
代码如下：

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<cmath>
#include<string>
using namespace std;
const long long hs=29987;
long long n,m,ex,ey,now,last,ans;
long long a[13][13],h[13][13],l[13][13],head[200000],nex[200000],que[2][200000],val[2][200000],cnt[2],inc[13];
void init()
{
	memset(a,0,sizeof(a));
	memset(h,0,sizeof(h));
	memset(l,0,sizeof(l));
	memset(head,0,sizeof(head));	
	memset(nex,0,sizeof(nex));	 
	memset(que,0,sizeof(que));
	memset(val,0,sizeof(val));
	memset(cnt,0,sizeof(cnt));
	memset(inc,0,sizeof(inc)); 
	string str;
	scanf("%lld%lld",&n,&m);
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			a[i][j]=1;
		}
	}
	ex=n;
	ey=m;
	getline(cin,str);
	getline(cin,str);
	ans=0;
	for (int i=1;i<=n-1;i++)
	{
		char ch=getchar();
		while (ch!='#') ch=getchar();
		for (int j=1;j<=m-1;j++)
		{
			scanf("%d",&h[i][j]);
			ans=ans+abs(h[i][j]);
		}
		getline(cin,str);
		for (int j=1;j<=m;j++)
		{
			ch=getchar();
			while (ch!='#') ch=getchar();
			scanf("%d",&l[i][j]);
			ans=ans+abs(l[i][j]);
		} 
		getline(cin,str);
	}
	char ch=getchar();
	while (ch!='#') ch=getchar();
	for (int j=1;j<=m-1;j++)
	{
		scanf("%d",&h[n][j]);
		ans=ans+abs(h[n][j]);
	}
	getline(cin,str);
	getline(cin,str); 
	inc[0]=1;
	for(int i=1;i<=13;i++)
	{
       inc[i]=inc[i-1]<<2;
	}
}
inline void insert(long long bit,long long num)
{
   long long u=bit%hs+1;
   for(int i=head[u];i;i=nex[i])
   {
       if(que[now][i]==bit)
	   {
           if (val[now][i]>num) val[now][i]=num;
           return;
       }
   }
   nex[++cnt[now]]=head[u];
   head[u]=cnt[now];
   que[now][cnt[now]]=bit;
   val[now][cnt[now]]=num;
}
inline void solve()
{
	cnt[now]=1; 
	val[now][1]=0; 
	que[now][1]=0;
	for(int i=1;i<=n;i++)
	{
    	for(int j=1;j<=cnt[now];j++)
    	{
        	que[now][j]<<=2;
    	}
       	for(int j=1;j<=m;++j)
	   	{
        	memset(head,0,sizeof(head));
        	last=now; now^=1;
           	cnt[now]=0;
        	for(int k=1;k<=cnt[last];++k)
			{
				long long bit=que[last][k],num=val[last][k];
				long long b1=(bit>>((j-1)*2))%4,b2=(bit>>(j*2))%4;
               	if (b1) num=num+h[i][j-1];
               	if (b2) num=num+l[i-1][j];
			   	if(!b1&&!b2)
				{
                   	if(a[i+1][j]&&a[i][j+1]) insert(bit+inc[j-1]+inc[j]*2,num);
               	}
				else if(!b1&&b2)
				{
                   	if(a[i][j+1]) insert(bit,num);
                   	if(a[i+1][j]) insert(bit-inc[j]*b2+inc[j-1]*b2,num);
               	}
				else if(b1&&!b2)
				{
                   	if(a[i+1][j]) insert(bit,num);
                   	if(a[i][j+1]) insert(bit-inc[j-1]*b1+inc[j]*b1,num);
               	}
				else if(b1==1&&b2==1)
				{
                   	int flag=1;
                   	for(int l=j+1;l<=m;++l)
					{
                       	if((bit>>(l*2))%4==1) flag++;
                       	if((bit>>(l*2))%4==2) flag--;
                       	if(!flag)
						{
                           	insert(bit-inc[j]-inc[j-1]-inc[l],num);
                           	break;
                       	}
                   	}
               	}
				else if(b1==2&&b2==2)
				{
                   	int flag=1;
                   	for(int l=j-2;l>=0;--l)
				   	{
                       	if((bit>>(l*2))%4==1) flag--;
                       	if((bit>>(l*2))%4==2) flag++;
                       	if(!flag)
						{
                           	insert(bit-inc[j]*2-inc[j-1]*2+inc[l],num);
                           	break;
                       	}
                   	}
               	}
				else if(b1==2&&b2==1) insert(bit-inc[j-1]*2-inc[j],num);
					else if(i==ex&&j==ey) if (num<ans) ans=num;
           	}
       	}
   	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while (t--)
	{
		init();
		solve();
		printf("%lld\n",ans);		
	}
	return 0;
}

poj 1739

题目大意：
有些格点必须走，有些不能走，问从左下角走到右下角多少种路径。
题目分析：
我们可以在最后加两行，第一行只有头尾可走，第二行全部可走，然后就转换为了回路问题。楼教主男人八题之一，不过记得调一下hash参数。1e5会tle，1e4就行了。
代码如下：

#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
const long long hs=29987;
long long n,m,ex,ey,now,last,ans;
long long a[13][13],head[300010],nex[300010],que[2][300010],val[2][300010],cnt[2],inc[13];
void init()
{
	ans=0;
	memset(a,0,sizeof(a));
	memset(head,0,sizeof(head));	
	memset(nex,0,sizeof(nex));	 
	memset(que,0,sizeof(que));
	memset(val,0,sizeof(val));
	memset(cnt,0,sizeof(cnt));
	memset(inc,0,sizeof(inc)); 
	scanf("%lld%lld",&n,&m);
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			char ch=getchar();
			while (ch!='#'&&ch!='.') ch=getchar();
			if (ch!='.') a[i][j]=0;
			else 
			{
				a[i][j]=1;
			}
		}
	}
	string str;
	a[n+1][1]=1;
	a[n+1][m]=1;
	for (int j=2;j<=m-1;j++)
	{
		a[n+1][j]=0;
	}
	for (int j=1;j<=m;j++)
	{
		a[n+2][j]=1;
	}
	n=n+2;
	ex=n;
	ey=m;
	inc[0]=1;
	for(int i=1;i<=13;i++)
	{
       inc[i]=inc[i-1]<<2;
	}
}
inline void insert(long long bit,long long num)
{
   long long u=bit%hs+1;
   for(int i=head[u];i;i=nex[i])
   {
       if(que[now][i]==bit)
	   {
           val[now][i]+=num;
           return;
       }
   }
   nex[++cnt[now]]=head[u];
   head[u]=cnt[now];
   que[now][cnt[now]]=bit;
   val[now][cnt[now]]=num;
}
inline void solve()
{
	cnt[now]=1; 
	val[now][1]=1; 
	que[now][1]=0;
	for(int i=1;i<=n;i++)
	{
    	for(int j=1;j<=cnt[now];j++)
    	{
        	que[now][j]<<=2;
    	}
       	for(int j=1;j<=m;++j)
	   	{
        	memset(head,0,sizeof(head));
        	last=now; now^=1;
           	cnt[now]=0;
        	for(int k=1;k<=cnt[last];++k)
			{
               	long long bit=que[last][k],num=val[last][k];
               	long long b1=(bit>>((j-1)*2))%4,b2=(bit>>(j*2))%4;
               	if(!a[i][j])
			   	{
                   if(!b1&&!b2) insert(bit,num);
               	}
			   	else if(!b1&&!b2)
				{
                   	if(a[i+1][j]&&a[i][j+1]) insert(bit+inc[j-1]+inc[j]*2,num);
               	}
				else if(!b1&&b2)
				{
                   	if(a[i][j+1]) insert(bit,num);
                   	if(a[i+1][j]) insert(bit-inc[j]*b2+inc[j-1]*b2,num);
               	}
				else if(b1&&!b2)
				{
                   	if(a[i+1][j]) insert(bit,num);
                   	if(a[i][j+1]) insert(bit-inc[j-1]*b1+inc[j]*b1,num);
               	}
				else if(b1==1&&b2==1)
				{
                   	int flag=1;
                   	for(int l=j+1;l<=m;++l)
					{
                       	if((bit>>(l*2))%4==1) flag++;
                       	if((bit>>(l*2))%4==2) flag--;
                       	if(!flag)
						{
                           	insert(bit-inc[j]-inc[j-1]-inc[l],num);
                           	break;
                       	}
                   	}
               	}
				else if(b1==2&&b2==2)
				{
                   	int flag=1;
                   	for(int l=j-2;l>=0;--l)
				   	{
                       	if((bit>>(l*2))%4==1) flag--;
                       	if((bit>>(l*2))%4==2) flag++;
                       	if(!flag)
						{
                           	insert(bit-inc[j]*2-inc[j-1]*2+inc[l],num);
                           	break;
                       	}
                   	}
               	}
				else if(b1==2&&b2==1) insert(bit-inc[j-1]*2-inc[j],num);
					else if(i==ex&&j==ey) ans+=num;
           	}
       	}
   	}
}
int main()
{
   	while (1)
   	{
		init();
		if (n==2&&m==0) break;
   		solve();
   		printf("%lld\n",ans);
   	}
   	return 0;
}

hdu 4285

题目大意：
n*m的棋盘，有些格子不能走，有些必须走。问没有回路套回路且总共k条回路方案数。
题目分析：
这个题目调了一会儿哈希，mle了一会儿。最后把nex，head数组，longlong变int，qaq。
题目有两个变化，第一个是k条回路，好处理。压进状态里就行了。另一个是回路套回路，让某个回路合拢时，左侧括号时奇数个，则出现了回路套回路，因为总数为偶数，左侧为奇数则右侧也为奇数。每次合拢只能在一边消去2个，最后一定是回路套回路。这个题目最小表示时限勉强，括号匹配无压力。
代码如下：

/*
bit最高三位用来标记k
(m+1)个位用来标记插头 
*/
#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
const long long hs=199987;
const long long mod=1e9+7;
long long n,m,ex,ey,now,last,ans,sk;
int a[15][15],head[800010],nex[800010],que[2][800010],cnt[2],inc[15];
long long val[2][800010];
void init()
{
	ans=0;
	memset(a,0,sizeof(a));
	memset(head,0,sizeof(head));	
	memset(nex,0,sizeof(nex));	 
	memset(que,0,sizeof(que));
	memset(val,0,sizeof(val));
	memset(cnt,0,sizeof(cnt));
	memset(inc,0,sizeof(inc)); 
	scanf("%lld%lld%lld",&n,&m,&sk);
	if (sk>36) sk=37; 
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			char ch=getchar();
			while (ch!='*'&&ch!='.') ch=getchar();
			if (ch!='.') a[i][j]=0;
			else 
			{
				a[i][j]=1;
				ex=i;
				ey=j;
			}
		}
	}
	inc[0]=1;
	for(int i=1;i<=14;i++)
	{
       inc[i]=inc[i-1]<<2;
	}
}
inline void insert(long long bit,long long num)
{
   long long u=bit%hs+1;
   for(int i=head[u];i;i=nex[i])
   {
       if(que[now][i]==bit)
	   {
           val[now][i]=(val[now][i]+num)%mod;
           return;
       }
   }
   nex[++cnt[now]]=head[u];
   head[u]=cnt[now];
   que[now][cnt[now]]=bit;
   val[now][cnt[now]]=num;
}
inline void solve()
{
	cnt[now]=1; 
	val[now][1]=1; 
	que[now][1]=0;
	for(int i=1;i<=n;i++)
	{
    	for(int j=1;j<=cnt[now];j++)
    	{
    		long long t=que[now][j]/inc[m+1];
        	que[now][j]=((que[now][j]-t*inc[m+1])<<2)+t*inc[m+1];
    	}
       	for(int j=1;j<=m;++j)
	   	{
        	memset(head,0,sizeof(head));
        	last=now; now^=1;
           	cnt[now]=0;
//          cout<<i<<" "<<j<<"   ："<<endl;
//			cout<<"--------------"<<endl; 
        	for(int k=1;k<=cnt[last];++k)
			{
               	long long bit=que[last][k],num=val[last][k];
               	long long b1=(bit>>((j-1)*2))%4,b2=(bit>>(j*2))%4,t=bit/inc[m+1];
//               	cout<<bit<<endl;
//               	cout<<b1<<" "<<b2<<" "<<t<<endl; 
//               	cout<<"-----------------"<<endl;
               	if(!a[i][j])
			   	{
                   if(!b1&&!b2) insert(bit,num);
               	}
			   	else if(!b1&&!b2)
				{
                   	if(a[i+1][j]&&a[i][j+1]) insert(bit+inc[j-1]+inc[j]*2,num);
               	}
				else if(!b1&&b2)
				{
                   	if(a[i][j+1]) insert(bit,num);
                   	if(a[i+1][j]) insert(bit-inc[j]*b2+inc[j-1]*b2,num);
               	}
				else if(b1&&!b2)
				{
                   	if(a[i+1][j]) insert(bit,num);
                   	if(a[i][j+1]) insert(bit-inc[j-1]*b1+inc[j]*b1,num);
               	}
				else if(b1==1&&b2==1)
				{
                   	int flag=1;
                   	for(int l=j+1;l<=m;++l)
					{
                       	if((bit>>(l*2))%4==1) flag++;
                       	if((bit>>(l*2))%4==2) flag--;
                       	if(!flag)
						{
                           	insert(bit-inc[j]-inc[j-1]-inc[l],num);
                           	break;
                       	}
                   	}
               	}
				else if(b1==2&&b2==2)
				{
                   	int flag=1;
                   	for(int l=j-2;l>=0;--l)
				   	{
                       	if((bit>>(l*2))%4==1) flag--;
                       	if((bit>>(l*2))%4==2) flag++;
                       	if(!flag)
						{
                           	insert(bit-inc[j]*2-inc[j-1]*2+inc[l],num);
                           	break;
                       	}
                   	}
               	}
				else if(b1==2&&b2==1) insert(bit-inc[j-1]*2-inc[j],num);
				else
				{
					int flag=0;
					for (int jj=0;jj<=j-2;jj++)
					{
						if ((bit>>((jj)*2))%4!=0) flag=1-flag;
					}
					if (flag) continue;
					if (t==sk-1&&i==ex&&j==ey) ans=(ans+num)%mod;
						else insert(bit-inc[j-1]-inc[j]*2+inc[m+1],num);
				}
           	}
       	}
   	}
}
int main()
{
	int t;
	scanf("%d",&t); 
	while(t--)
	{
   		init();
   		solve();
   		printf("%lld\n",ans);
   	}
   	return 0;
}

电脑前这个努力的帅气身影是谁呢？そう 私 です

本文地址：https://blog.csdn.net/hollyidyllic/article/details/110131256