最后一个点一直过不去,求求了
查看原帖
最后一个点一直过不去,求求了
295543
beauty_son_whm楼主2022/1/28 19:40
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
string s[12],a[12];
int tot=0;
int b[12];
string g[12][1<<12];
basic_string<int>To[1<<12];
basic_string<int>Fr[1<<12];
bool check(string x,string y){
	if(x==y) return 0;
	if(y.find(x)==string::npos) return 0;
	return 1;
}
string calc(string x, string y){
	int l1=x.size(),l2=y.size();
	string ans;
	int chong=0;
	for(int i=1;i<=l2&&i<=l1;i++){
		string c1=y.substr(0,i),c2=x.substr(l1-i,i);
		if(c1==c2) chong=i;
	}
	for(int i=0;i<l1;i++) ans+=x[i];
	for(int i=chong;i<l2;i++) ans+=y[i];
	return ans;
}
void init(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>s[i];
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i!=j){
				if(check(a[i],a[j])){
					b[i]=1;
				}
			}
		}
	}
	for(int i=0;i<n;i++){
		if(b[i]==0){
			a[tot++]=s[i];
		}
	}
	n=tot;
	for(int sta=0;sta<(1<<n);sta++){
		for(int i=0;i<n;i++){
			if(((sta>>i)&1)==1){
				To[sta]+=i;
			}else Fr[sta]+=i;
		}
	}
}
void DP(){
	for(int i=0;i<n;i++){
		g[i][1<<i]=a[i];
	}
	for(int sta=0;sta<(1<<n);sta++){
		for(int i:To[sta]){
			if(g[i][sta].size())
			for(int j:Fr[sta]){
				int nxt=sta|(1<<j);
				string tmp=calc(g[i][sta],a[j]);
				if(g[j][nxt].size()==0){
					g[j][nxt]=tmp;continue;
				}
				if(tmp.size()<g[j][nxt].size()) g[j][nxt]=tmp;
				
				else if(tmp.size()==g[j][nxt].size()){
					int pd=g[j][nxt].compare(tmp);
					if(pd==1){
						g[j][nxt]=tmp;
					}					
				}
			}
		}
	}
	int tep=INT_MAX;
	string s;
	for(int i=0;i<n;i++){
		int len=g[i][(1<<n)-1].size();
		if(tep>len){
			tep=len;s=g[i][(1<<n)-1];
		}
	}
	for(int i=0;i<n;i++){
		if(g[i][(1<<n)-1].size()==tep){
			s=min(s,g[i][(1<<n)-1]);
		}
	}
	cout<<s<<endl;
}
signed main(){
	init();
	DP();
	return 0;
}
/*
4
ABABA
AKAKA
AKABAS
ABAKA

*/
2022/1/28 19:40
加载中...