【XVII Open Cup E.V. Pankratiev. Grand Prix of Europe. D】Dancing Disks 题解

题目大意

  有一个 $6 \times 6$ 的网格图，每个格子上有一根柱子。
  现在有 $n$ 个盘子套在 $(1,1)$ 的柱子上，自底向上分别为 $a_1,a_2,\cdots,a_n$（构成一个大小为 $n$ 的排列）。
  每次操作你可以选择一根柱子，将其最上面的连续若干个盘子拿起，往下走一格或往右走一格。
  请构造一种方案使得盘子最后有序套在 $(6,6)$（自底向上是 $n,n-1,\cdots,1$）。

  $n \leq 40000$

题解

  假设现在要处理 $(x,y)$ 上的大小在 $[l,r]$ 之间的盘子（我们设计方案让每次处理的盘子的大小都是一段连续区间），我们肯定是要将它们分摊到其他地方，分治下去。
  具体来说，以 $(x,y)$ 为左上角、$(6,6)$ 为右下角的矩形（除去 $(x,y)$ 本身）都是可以用来分摊的，至于每个格子分摊多少，要看它的容量，即从它开始最多可以把多少个盘子排序。

  设 $f_{x,y}$ 表示 $(x,y)$ 的容量。显然 $f_{6,6}=1$。按照上面的分摊思想，可以得出

$$f_{x,y}=\sum_{i=x}^6\sum_{j=y}^6 [(i,j)\not=(x,y)] f_{i,j}$$

  于是就根据每个格子的容量安排它需要处理的大小区间，把当前 $(x,y)$ 的柱子一个个放到相应的格子去就好了。

  还剩一个问题是，如果容量直接按那个递推式来搞的话，$f_{1,1}$ 只有两万多，是不够 $n$ 大的。因此特殊考虑 $f_{5,6}$ 和 $f_{6,5}$，它们按照那个式子算的是 $1$，但实际可以处理 $2$ 个盘子，所以把这个初值也加上去的话 $f_{1,1}$ 就够大了。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

const int maxn=40005;

int n,f[8][8];
vector<int> a;

void Move(int x1,int y1,int x2,int y2,int num)
{
	fo(i,x1,x2-1) printf("%d %d D %d\n",i,y1,num);
	fo(j,y1,y2-1) printf("%d %d R %d\n",x2,j,num);
}

void dfs(int x,int y,vector<int> a,int l,int r)
{
	if (x==6 && y==6) return;
	if (x+y==11)
	{
		if (a.size()==1) Move(x,y,6,6,1); else
		{
			if (a[0]>a[1]) Move(x,y,6,6,2);
				else Move(x,y,6,6,1), Move(x,y,6,6,1);
		}
		return;
	}
	vector<int> ned[7][7];
	int lo[7][7],hi[7][7];
	int now=r;
	fd(i,6,x)
	{
		fd(j,6,y)
		{
			lo[i][j]=max(l,now-f[i][j]+1);
			hi[i][j]=now;
			now-=hi[i][j]-lo[i][j]+1;
			ned[i][j].clear();
			if (now<l) break;
		}
		if (now<l) break;
	}
	for(int k=a.size()-1; k>=0; k--)
	{
		int e=a[k];
		bool pd=0;
		fd(i,6,x)
		{
			fd(j,6,y) if (lo[i][j]<=e && e<=hi[i][j])
			{
				ned[i][j].push_back(e);
				Move(x,y,i,j,1);
				pd=1; break;
			}
			if (pd) break;
		}
	}
	now=r;
	fd(i,6,x)
	{
		fd(j,6,y)
		{
			dfs(i,j,ned[i][j],lo[i][j],hi[i][j]);
			now-=hi[i][j]-lo[i][j]+1;
			if (now<l) break;
		}
		if (now<l) break;
	}
}

int main()
{
	//freopen("d.in","r",stdin);
	//freopen("d.out","w",stdout);
	
	scanf("%d",&n);
	fo(i,1,n)
	{
		int x;
		scanf("%d",&x);
		a.push_back(x);
	}
	
	f[6][6]=1;
	f[5][6]=f[6][5]=2;
	f[5][5]=5;
	fd(i,6,1)
		fd(j,6,1) if (i<5 || j<5)
			fo(x,i,6)
				fo(y,j,6) f[i][j]+=f[x][y];
	
	dfs(1,1,a,1,n);
}