bzoj 1210 [HNOI2004] 邮递员插头dp

插头dp板子题？？

搞了我一晚上，还tm全是抄的标程。。

还有高精，哈希混入，还是我比较弱，orz各种dalao

有不明白的可以去看原论文。。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#define base (int)1e9

#define maxh 2650

using namespace std;

int n,m;

int get(int s,int x){

	return (s>>((x-1)<<1))&3;

}//查询对于状态s,第x位的状态. 三进制,所以左移一位.&3,得0,1,2

void change(int &s,int x,int y){

	int w=(x-1)<<1;

	s&=~(3<<w);

	s|=y<<w;

}//将s状态的第x位改为y

int find(int s,int x){

	for(int i=x,d=0,pos=get(s,x)==1?1:-1;;i+=pos){

		int nn=get(s,i);

		if(nn==1) d++; if(nn==2) d--;

		if(!d) return i;

	}

}//找与该位匹配的括号

struct bignum{//高精没啥好说的...

	int a[5];

	void clear(){memset(a,0,sizeof a);}

	bignum(){clear();}

	void set(int x){clear();while(x){a[++a[0]]=x%base;x/=base;}}

	void print(){

		printf("%d",a[a[0]]);

		for(int i=a[0]-1;i>0;i--)printf("%09d",a[i]);

	}

	bignum operator + (bignum b){

		static bignum c;c.clear();c.a[0]=max(a[0],b.a[0])+1;

		for(int i=1;i<=c.a[0];i++){

			c.a[i]+=a[i]+b.a[i];

			c.a[i+1]+=c.a[i]/base;

			c.a[i]%=base;

		}

		while(!c.a[c.a[0]])c.a[0]--;

		return c;

	}

	void operator += (bignum b){*this=*this+b;}

	void operator = (int x){set(x);}

}ans;

struct hashtable{//骚骚的哈希

	int key[maxh];

	int cnt,hash[maxh];

	bignum val[maxh];

	void clear(){

		memset(key,-1,sizeof key);

		memset(hash,0,sizeof hash);

		memset(val,0,sizeof val);

		cnt=0;

	}

	void newnode(int i,int x){

		hash[i]=++cnt;

		key[cnt]=x;

	}

	bignum & operator[](const int hh){

		int k;

		for(int i=hh%maxh;;i++){

			if(i==maxh)i=0;

			if(!hash[i]) newnode(i,hh);

			if(key[hash[i]]==hh){k=hash[i]; break;}

		}

		return val[k];

	}

}f[2];

int now,last;

void dp(int i,int j){//插头dp

	now^=1;last^=1;

	int tot=f[last].cnt;

	f[now].clear();

	for(int k=1,x,y;k<=tot;k++){

		int s=f[last].key[k];

		bignum vv=f[last].val[k];

		x=get(s,j); y=get(s,j+1);

		if(!x&&!y){if(i!=n&&j!=m){change(s,j,1);change(s,j+1,2);f[now][s]+=vv;}}

		else if(x==1&&y==1){

			change(s,find(s,j+1),1);

			change(s,j,0); change(s,j+1,0);

			f[now][s]+=vv;

		}

		else if(x==2&&y==2){

			change(s,find(s,j),2);

			change(s,j,0); change(s,j+1,0);

			f[now][s]+=vv;

		}

		else if(x==1&&y==2){

			if(i==n&&j==m) ans+=vv;

		}

		else if(x==2&&y==1){

			change(s,j,0); change(s,j+1,0);

			f[now][s]+=vv;

		}

		else if(x){

			if(i!=n) f[now][s]+=vv;

			if(j!=m){change(s,j,0);change(s,j+1,x);f[now][s]+=vv;}

		}

		else if(y){

			if(j!=m) f[now][s]+=vv;

			if(i!=n){change(s,j+1,0);change(s,j,y);f[now][s]+=vv;}

		}

	}

}

int main(){

    freopen("postman.in","r",stdin);

    freopen("postman.out","w",stdout);

	scanf("%d%d",&n,&m);

	if(n==1||m==1){printf("1\n");return 0;}

	if(n<m)swap(n,m);

	f[0][0]=1;

	now=0;last=1;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++)dp(i,j);

		if(i!=n)for(int j=1,k=f[now].cnt;j<=k;j++)

			f[now].key[j]<<=2;

	}

	ans+=ans;

	ans.print();

	return 0;

}

巴特西

bzoj 1210 [HNOI2004] 邮递员插头dp

最新文章

热门文章

巴特西

bzoj 1210 [HNOI2004] 邮递员 插头dp

最新文章

热门文章

bzoj 1210 [HNOI2004] 邮递员插头dp