脚本宝典收集整理的这篇文章主要介绍了【洛谷3681】[CERC2016] Dancing Disks（归并），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题目链接

• 有一张 (6times 6) 的网格图，初始 (n) 个盘子堆在 ((1,1))，从下往上依次为 (a_{1sim n})。
• 一次操作可以把某个格子中最上方若干个盘子按顺序移到右方或下方格子中的最上方。
• 要求构造一种方案将所有盘子移到 ((6,6))，且满足从下往上 (a_i) 递增。
• (1le nle 4times10^4)

归并思想

考虑设 (f_{i,j}) 表示通过若干操作最多能在 ((i,j)) 保证多少个盘子有序。

特殊地，(f_{1,1}=1)；((1,2)) 和 ((2,1)) 可以根据 ((1,1)) 最上面两个盘子的大小选择一起移动或分别移动实现有序，所以 (f_{1,2}=f_{2,1}=2)。

而对于一般的格子 ((x,y))，它可以从所有格子 ((i,j) (1le ile x,1le jle y)) 归并得到，即 (f_{x,y}=sum_{1le ile x,1le jle y}f_{i,j})。

然后发现这样求出的 (f_{6,6}=42960)，能够满足条件。

递归的具体实现

具体实现就考虑一个递归的过程。注意，若想让当前盘子自下往上递增，需要让先前盘子自下往上递减。

按自下往上、自右往左的顺序搞可能会方便一些，因为右下方的格子在求解的过程中会用到左上方的格子。

每次就是把当前格子需要的份额分给先前的格子。当然，肯定不能超过每个格子对应的 (f_{i,j})。

然后用一个堆维护归并的过程，但数据范围这么小直接暴力似乎也行。

代码：(O(36nLOG36))

#include<bITs/stdc++.h>
#define Tp template<tyPEname Ty>
#define Ts template<typename Ty,typename... Ar>
#define Rg register
#define RI Rg int
#define Cn const
#define CI Cn int&amp;
#define I inline
#define W while
#define N 40000
using namespace std;
int n,tp,a[N+5],f[7][7],g[7][7];vector<int> p[7][7];
I void M(CI x1,CI y1,CI x2,CI y2) {for(RI i=x1;i^x2;++i) PRintf("%d %d D 1n",i,y1);for(RI i=y1;i^y2;++i) printf("%d %d R 1n",x2,i);}
priority_queue<pair<int,int> > q[7][7];I void Solve(CI x,CI y,RI sz,CI op)//递归
{
	if(x==1&&y==1) return p[x][y].push_back(a[tp--]);//特判(1,1)
	if(x==1&&y==2)//特判(1,2)
	{
		if(sz==1) return puts("1 1 R 1"),p[x][y].push_back(a[tp--]);//只需一个
		if(op*a[tp-1]>op*a[tp]) return puts("1 1 R 2"),tp-=2,p[x][y].push_back(a[tp+1]),p[x][y].push_back(a[tp+2]);//一起移动
		return puts("1 1 R 1"),puts("1 1 R 1"),p[x][y].push_back(a[tp--]),p[x][y].push_back(a[tp--]);//分别移动
	}
	if(x==2&&y==1)//特判(2,1)
	{
		if(sz==1) return puts("1 1 D 1"),p[x][y].push_back(a[tp--]);//只需一个
		if(op*a[tp-1]>op*a[tp]) return puts("1 1 D 2"),tp-=2,p[x][y].push_back(a[tp+1]),p[x][y].push_back(a[tp+2]);//一起移动
		return puts("1 1 D 1"),puts("1 1 D 1"),p[x][y].push_back(a[tp--]),p[x][y].push_back(a[tp--]);//分别移动
	}
	#define PUSH(i,j) q[x][y].push(make_pair(op*p[i][j].back(),i*6+j-1))//将(i,j)最上方的盘子入堆
	RI i,j;for(i=x;i;--i) for(j=y;j;--j) if(i^x||j^y) if(Solve(i,j,min(sz,f[i][j]),-op),PUSH(i,j),(sz-=f[i][j])<=0) goto Calc;//将需要份额分给先前格子，注意反序
	Calc:pair<int,int> k;W(!q[x][y].empty()) k=q[x][y].top(),q[x][y].pop(),//取出堆顶
		p[x][y].push_back(k.First/op),i=k.second/6,j=k.second%6+1,M(i,j,x,y),p[i][j].pop_back(),!p[i][j].empty()&&(PUSH(i,j),0);//放入对应位置新的最上方盘子
}
int main()
{
	RI i,j;for(scanf("%d",&n),i=1;i<=n;++i) scanf("%d",a+i);
	for(i=1;i<=6;++i) for(j=1;j<=6;++j)
	{
		if(i==1&&j==1) {f[i][j]=g[i][j]=1;continue;}if(i==1&&j==2||i==2&&j==1) {f[i][j]=2,g[i][j]=3;continue;}//特判(1,1),(1,2),(2,1)
		f[i][j]=g[i-1][j]+g[i][j-1]-g[i-1][j-1],g[i][j]=f[i][j]<<1;//一般情况
	}return tp=n,Solve(6,6,n,1),0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的【洛谷3681】[CERC2016] Dancing Disks（归并）全部内容，希望文章能够帮你解决【洛谷3681】[CERC2016] Dancing Disks（归并）所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。