题解：P5215 [SHOI2014] 神秘金字塔

这题通过率低的原因是因为题目难读懂吗。

题目要求每层的连通块都满足上下对称与左右对称，所以考虑将联通块分成四等份，我们只用算其中的一个部分即可。

假定我们算左上角的部分，根据题目的限制，这个联通块一定满足以下条件：

形状为阶梯；
长、宽均为 $\frac{l_i}{2}$ 。

容易发现，当

l_i=20

时，满足以上条件的连通块个数为

\binom{18}{9}=48620

。

状态数是相对比较少的。

考虑 dp，并把连通块状态设进 dp 状态里。

先将所有连通块状态爆搜出来，然后依次编号，接着我们设

f_{i,j,s}

表示放完了前

i

层，当前用了

j

个点，现在的连通块状态为

s

的方案数。

考虑转移，我们发现

s

的转移本质上是包含关系，所以预处理

s

的关系后直接用高维后缀和优化即可。

时间复杂度

O(hnlS)

，其中

S

为同一边长的连通块的最大状态数。虽然这东西算出来很大，但实际上

n

带有

\frac{1}{4}

常数，

l

带有

\frac{1}{2}

常数，且

S

跑不满，数组内存访问比较连续，所以跑的并不慢。

CPP

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;bool f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int Maxn=1005,N=66199,mod=1e9+7;
inline void add(int&x,int y){(x+=y)>=mod?x-=mod:0;}
int n,m,a[11];
int tot=0,val[N];
map<vector<int>,int>idx;
vector<int>tpp;
int up[N],nxt[11][N];
int L[11],R[11];
void dfs(int x,int now,int nn){
	if(x==nn+1){
		idx[tpp]=++tot;
		for(int i=0;i<nn;i++)val[tot]+=tpp[i];
		vector<int>tp;
		if(nn<a[0]){
			tp.emplace_back(1);
			for(int i=0;i<nn-1;i++)tp.emplace_back(tpp[i]);
			tp.emplace_back(nn+1);
			up[tot]=idx[tp];
		}
		for(int i=1;i<=nn;i++){
			if(tpp[i-1]>1&&(i==1||tpp[i-1]>tpp[i-2])){
				--tpp[i-1];
				nxt[i][tot]=idx[tpp];
				++tpp[i-1];
			}
		}
		return;
	}
	for(int i=(x==nn?nn:now);i<=nn;i++){
		tpp.emplace_back(i);
		dfs(x+1,i,nn);
		tpp.pop_back();
	}
}
int f[N][255],sum[N][255];
inline int get(int o,int s){
	for(int i=a[o];i<a[o-1];i++)s=up[s];
	return s;
}
int main(){
//	freopen("score.in","r",stdin);
//	freopen("score.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=m;i++)a[i]=read()/2;
	a[0]=a[1];
	for(int i=a[0];i;i--){
		L[i]=tot+1;
		dfs(1,1,i);
		R[i]=tot;
	}for(int j=1;j<=R[a[0]];j++)sum[j][0]=1;
	if(n%4!=0)return void(puts("0")),0;
	n/=4;int all=0;
	for(int o=1;o<=m;o++){all+=a[o]*2-1;
		for(int s=L[a[o]];s<=R[a[o]];s++){
      int s0=get(o,s);
			for(int i=n;i>=val[s];i--)sum[s][i]=f[s][i]=sum[s0][i-val[s]];
			for(int i=0;i<val[s];i++)sum[s][i]=0;
    }
		for(int j=1;j<=a[o];j++)for(int s=R[a[o]];s>=L[a[o]];s--)if(nxt[j][s]){
			for(int i=all;i<=n;i++)add(sum[nxt[j][s]][i],sum[s][i]);
		}
	}
	printf("%d\n",sum[L[a[m]]][n]);
	return 0;
}

题解：P5215 [SHOI2014] 神秘金字塔

文章操作

相关推荐

评论

题解：P5215 [SHOI2014] 神秘金字塔