文章

10

粉丝

168

获赞

0

访问

51.9k

头像
迭代加深
P1162 清华大学上机题
发布于2022年3月6日 19:55
阅读数 5.4k

 

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF=1e9;
char s[20];
int n;
bool st[20];

int MAX;


bool first_judge(){
	int a[3]={0,0,0};
	for(int i=0;i<n;i++)
		a[s[i]-'0']++;
	if(a[2]<2 || a[0]<1 || a[1]<1)	return true;
	return false;
}

bool judge(){
	for(int i=0;i<n-3;i++)
		if(s[i]=='2' && s[i+1]=='0' && s[i+2]=='1' && s[i+3]=='2')
			return true;
	return false;
}

bool dfs(int num,int idx){
	if(judge()){
		return true;
	}
	if(num+1>MAX)	return false;
	for(int i=0;i<n-1;i++){
		if(i==idx)	continue;
		swap(s[i],s[i+1]);
		if(dfs(num+1,i))	return true;
		swap(s[i],s[i+1]);
	}
	return false;
}

int main(){
	while(cin>>n>>s){
		if(first_judge()){
			cout<<-1<<'\n';
			continue;
		}
		memset(st,false,sizeof st);
		MAX=0;
		while(!dfs(0,-1))	MAX++;
		cout<<MAX<<'\n';
	}
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发