wsh大佬讲的很对

但是有hack

这份代码可以通过全部样例

code:

#include <bits/stdc++.h>
using namespace std;

const int N = 50;

int n, st[N], ed[N], now[N];
//读入 
void read(){
	scanf("%d",&n);
	for(int i = 1;i <= 3; i++){
		int k; scanf("%d",&k);
		for(int j = 1;j <= k; j++){
			int x; scanf("%d",&x);
			st[x] = i;
		}
	}
	for(int i = 1;i <= 3; i++){
		int k; scanf("%d",&k);
		for(int j = 1;j <= k; j++){
			int x; scanf("%d",&x);
			ed[x] = i;
		}
	}
}

string c = " ABC";

int cnt[2];
//移动，id是哪个盘子，u是从哪来，v是到哪去，op是第几种方法，p是是否打印 
void dfs(int id,int u,int v,int op,int p){
	if(u == v) return ;
	for(int i = id - 1;i >= 1; i--) dfs(i,now[i],6-u-v,op,p);
	if(p) printf("move %d from %c to %c\n",id,c[u],c[v]);
	if(!p) cnt[op]++;
	now[id] = v;
}

void compute(){
	//直接往目标方向移动 
	for(int i = 1;i <= n; i++) now[i] = st[i];
	for(int i = n;i >= 1; i--) dfs(i,now[i],ed[i],0,0);
	//先移到中间再去往目标方向移动 
	for(int i = 1;i <= n; i++) now[i] = st[i];
	dfs(n,now[n],6-now[n]-ed[n],1,0);
	for(int i = n;i >= 1; i--) dfs(i,now[i],ed[i],1,0);
	//输出 
	for(int i = 1;i <= n; i++) now[i] = st[i];
	if(cnt[0] < cnt[1]){
		for(int i = n;i >= 1; i--) dfs(i,now[i],ed[i],0,1);
		printf("%d",cnt[0]);
	}
	else{
		dfs(n,now[n],6-now[n]-ed[n],1,1);
		for(int i = n;i >= 1; i--) dfs(i,now[i],ed[i],1,1);
		printf("%d",cnt[1]);
	}
	return ;
}

int main(){
	read();
	compute();
	return 0;
}

首先读完题目我们发现任何时刻都不允许大盘子叠放在小盘子上面

那么我们考虑搜索

我们用两个数组记录一下每个盘子一开始在几号柱子，目标到几号柱子

然后再从大到小来搜索把每一个盘子放到目标位置

但是在搜索的时候若当前要移编号为 $i$ 的盘子，要把编号为 $1->i$ 全部移走

void dfs(int idx,int idy){
	if(a[idx]==idy) return;
	for(int i=idx-1;i>=1;i--){
		if(a[idx]==1&&idy==2) dfs(i,3);
		else if(a[idx]==2&&idy==3) dfs(i,1);
		else if(a[idx]==1&&idy==3) dfs(i,2);
		else if(a[idx]==3&&idy==1) dfs(i,2);
		else if(a[idx]==3&&idy==2) dfs(i,1);
		else if(a[idx]==2&&idy==1) dfs(i,3);
	}
	ans++;
	printf("move %lld from %c to %c\n",idx,s[a[idx]],s[idy]);
	a[idx]=idy;
}

非正确代码：

#include<cstdio>
int n,last[55],first[55],ans=0,m,x;
const char ch[]={' ','A','B','C'};
void dfs(int x,int y)
{
    if(first[x]==y) return;
    for(int i=x-1;i>=1;i--) dfs(i,6-(first[x]+y));
    //处理小盘子。
    printf("move %d from %c to %c\n",x,ch[first[x]],ch[y]);
    //输出。
    first[x]=y;ans++;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=3;i++)
    {
        scanf("%d",&m);
        for(int j=1;j<=m;j++) scanf("%d",&x),first[x]=i;
    }
    for(int i=1;i<=3;i++)
    {
        scanf("%d",&m);
        for(int j=1;j<=m;j++) scanf("%d",&x),last[x]=i;
    }
    //将每一个目标与初始柱打上标记
    for(int i=n;i>=1;i--) dfs(i,last[i]);
    //第i个要到目标柱那里去。
    printf("%d",ans);
    return 0;
}