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

思路

首先发现

l_i

一定为偶数，且左右上下对称，所以可以直接分成四半大小为

\frac{n}4

的部分，每层的最大宽度减半。

设第

i

列有

w_i

个数，根据题目限制，需要满足

w_i\ge w_{i+1}

，且

w_1=l,w_l\ge 1

。这个东西的个数并不多，具体的，当

l=10

时，状态数等于

\binom{18}{9}=48620

。

那么就可以 DP 了，设

f_{i,j,s}

表示第

i

层，用了

j

个方块，这一层的阶梯为

s

的方案数。

考虑从

i

转移到

i+1

，设

t

为最大一个阶梯使得长度为

l_{i+1}

且被

s

包含。先把

f_{i,j,s}

转移到

f_{i+1,j,t}

，然后再对每一个

j

做高维后缀和即可。最后处理每个阶梯对

j

的影响。

时间复杂度

O(hnlV)

，其中

V

表示不同的阶梯数量，最大为

48620

。算出来大约为

10^9

，不过常数被实现得特别优秀，可以通过。

细节

首先为了记录状态，我们需要对每一个

l

按字典序从小到大枚举阶梯，将每个阶梯映射到一个编号，这一步使用 map 即可。

预处理

mn_{i,s}

表示最大一个阶梯使得长度为

i

且被

s

包含。这个是简单的，

mn_{s,i}

的第

x

个位置等于

\min(s_x,i)

，套用上面的编号即可。

对于高维后缀和，我们需要预处理一个

del_{i,s}

表示

s

将第

i

位减一后到哪个区间。做高维后缀和的时候，直接从大到小枚举

i

，从大到小枚举

s

的编号，让

f_{x,y,del_{s,i}}

加上

f_{x,y,s}

即可。

常数小的原因是长度固定时，阶梯的编号是一个区间，内存访问较为连续，所以可以通过。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 7e4+5,mod = 1e9+7;
int cnt;
map<vector<int>,int> mp;
vector<int> now;
int lim,lt[N],rt[N],del[30][N],mn[30][N],sum[N]; 
void dfs(int x)
{
	if(x==lim)
	{
		mp[now] = ++cnt;
		mn[lim][cnt] = cnt;
		for(auto i:now) sum[cnt]+=i;
		if(!lt[lim]) lt[lim] = cnt;
		rt[lim] = cnt;
		for(int i = 1;i<lim;i++)
		{
			vector<int> tmp;
			for(int j = 0;j<i;j++)
				tmp.push_back(min(now[j],i));
			mn[i][cnt] = mp[tmp];
		}
		for(int i = 1;i<lim;i++)
		{
			if(now[i]>(i==lim-1?1:now[i+1]))
			{
				now[i]--;
				del[i][cnt] = mp[now];
				now[i]++;
			}
		}
		return;
	}
	for(int i = 1;i<=now[x-1];i++)
	{
		now[x] = i;
		dfs(x+1);
	}
}
vector<int> vec[N];
int n,h,a[N],f[2][255][N];
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	for(lim = 1;lim<=10;lim++)
	{
		now.resize(lim);
		now[0] = lim;
		dfs(1);
	}
	cin>>n>>h;
	if(n%4) return cout<<0,0;
	n/=4;
	for(int i = 1,x;i<=h;i++)
	{
		cin>>a[i];
		if(a[i]%2) return cout<<0,0;
		a[i]/=2;
		if(i==1)
		{
			for(int j = lt[a[i]];j<=rt[a[i]];j++)
				if(sum[j]<=n) f[1][sum[j]][j] = 1;
		}
		else
		{
			int now = (i&1);
			for(int j = 0;j<=n;j++)
				for(int k = lt[a[i]];k<=rt[a[i]];k++)
					f[now][j][k] = 0;
			for(int j = 0;j<=n;j++)
				for(int k = lt[a[i-1]];k<=rt[a[i-1]];k++)
					(f[now][j][mn[a[i]][k]]+=f[now^1][j][k])%=mod;
			for(int j = n;j;j--)
			{
				for(int x = a[i]-1;x;x--)
					for(int k = rt[a[i]];k>=lt[a[i]];k--)
						(f[now][j][del[x][k]]+=f[now][j][k])%=mod;
				for(int k = lt[a[i]];k<=rt[a[i]];k++)
				{
					if(j+sum[k]<=n) (f[now][j+sum[k]][k]+=f[now][j][k])%=mod;
					f[now][j][k] = 0;
				}
			}
		}
	}
	int ans = 0;
	for(int i = lt[a[h]];i<=rt[a[h]];i++)
		(ans+=f[h&1][n][i])%=mod;
	cout<<ans;
	return 0;
}

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

文章操作

思路

细节

代码

相关推荐

评论

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