车车题

每辆车的调度次数为

1 \sim 3

次，故枚举调度次数

n \sim 3n

进行搜索。只要能调度到下一位置就进行调度。

n \leq 15

还是会 T。进行剪枝：

路线是单向的，故到达出口就不能返回，每次判断若到达出口则跳出。
若剩余调度次数小于还没到出口的车数，则不能满足。
若当前位置没有车，直接跳出。

代码：

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pb push_back
const int N = 30;
int n, g[N], s[4][N], c[N], sta, l[N], r[N], a[N];
string str;
void d(int x) {
	if(s[3][c[3]]!=g[c[3]] || sta-x+1<c[0]+c[1]+c[2])
		return;
	if(x==sta+1 && !c[0]+c[1]+c[2]) {
		for(int i=1; i<x; ++i)
			cout<<char(a[i]+'a'-1)<<" "<<char(l[i]+'A')<<" "<<char(r[i]+'A')<<"\n";
		exit(0); //直接结束程序
	}
	if(x>sta)
		return;
	for(int i=0; i<=2; ++i)
		for(int j=i+1; j<=3 && c[i]; ++j) {
			int t=s[i][c[i]--];
			a[x]=s[j][++c[j]]=t;
			l[x]=i;
			r[x]=j;
			d(x+1);
			s[i][++c[i]]=t;
			--c[j]; //回溯
		}
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>str;
	str=" "+str;
	for(int i=1; i<=n; ++i)
		g[n-i+1]=str[i]-'a'+1, s[0][++c[0]]=i;
	for(sta=n; sta<=n*3; ++sta)
		d(1);
	cout<<"NO";
	return 0;
}

题解来之不易，麻烦点赞再走~

文章操作

相关推荐

评论

车车题