WA 60pts 求助
查看原帖
WA 60pts 求助
723238
wukaichen888楼主2023/3/12 07:42
#include<bits/stdc++.h>
using namespace std;
const int N=55,M=8205;
int n,l[N],tot,dis[N][N],f[M][N],las[M][N],ans=1e9,r;
char s[N][N],s1[N][N],s2[M][N][N],tmp[M];
bool flag,vis[N];
void dfs(int now,int g){
	if(!now) return ;
//	printf("%d %d\n",now,g);
	dfs(now^(1<<g),las[now][g]);
	if(now^(1<<g)){
		for(int i=dis[las[now][g]][g]+1;i<=l[g];i++)
			printf("%c",s1[g][i]);
	}
	else
		for(int i=1;i<=l[g];i++)
			printf("%c",s1[g][i]);
}
int main(){
	memset(f,0x3f3f3f3f,sizeof f);
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%s",s[i]+1);
	for(int i=0;i<n;i++)
		l[i]=strlen(s[i]+1);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(i^j)
				for(int p=1;p+l[i]-1<=l[j];p++){
					flag=1;
					for(int q=0;q<l[i];q++)
						if(s[i][q+1]^s[j][p+q]){
							flag=0;
							break;
						}
					if(flag){
						vis[i]=1;
						break;
					}
				}
	for(int i=0;i<n;i++)
		if(!vis[i]){
			for(int j=1;j<=l[i];j++)
				s1[tot][j]=s[i][j];
			l[tot]=l[i];
			tot++;
		}
	n=tot;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(i^j)
				for(int p=1;p<=l[i];p++){
					flag=1;
					for(int q=0;p+q<=l[i];q++)
						if(s1[i][p+q]^s1[j][q+1]){
							flag=0;
							break;
						}
					if(flag){
						dis[i][j]=l[i]-p+1;
						break;
					}
				}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++)
//			printf("%d ",dis[i][j]);
//		puts("");
//	}
	for(int i=0;i<n;i++){
		f[1<<i][i]=l[i];
		for(int j=1;j<=l[i];j++)
			s2[1<<i][i][j]=s1[i][j];
	}
	for(int i=1;i<(1<<n);i++)
		for(int j=0;j<n;j++)
			if(i&(1<<j))
				for(int p=0;p<n;p++)
					if(i&(1<<p))
						if(j^p)
							if(f[i][j]>f[i^(1<<j)][p]+l[j]-dis[p][j]){
//								puts("A1");
								f[i][j]=f[i^(1<<j)][p]+l[j]-dis[p][j],las[i][j]=p;
								for(int q=1;q<=f[i^(1<<j)][p];q++)
									s2[i][j][q]=s2[i^(1<<j)][p][q];
								for(int q=1;q<=l[j]-dis[p][j];q++)
									s2[i][j][f[i^(1<<j)][p]+q]=s1[j][dis[p][j]+q];
							}
							else
								if(f[i][j]==f[i^(1<<j)][p]+l[j]-dis[p][j]){
//									puts("A2");
									for(int q=1;q<=f[i^(1<<j)][p];q++)
										tmp[q]=s2[i^(1<<j)][p][q];
									for(int q=1;q<=l[j]-dis[p][j];q++)
										tmp[f[i^(1<<j)][p]+q]=s1[j][dis[p][j]+q];
									flag=1;
									for(int q=1;q<=f[i][j];q++)
										if(tmp[q]<s2[i][j][q])
											break;
										else
											if(tmp[q]>s2[i][j][q]){
												flag=0;
												break;
											}
									if(flag){
										las[i][j]=p;
										for(int q=1;q<=f[i][j];q++)
											s2[i][j][q]=tmp[q];
									}
								}
	for(int i=0;i<n;i++)
		if(ans>f[(1<<n)-1][i]){
			ans=f[(1<<n)-1][i];
			r=i;
		}
		else
			if(ans==f[(1<<n)-1][i]){
				flag=1;
				for(int j=1;j<=f[(1<<n)-1][i];j++)
					if(s2[(1<<n)-1][i][j]<s2[(1<<n)-1][r][j])
						break;
					else
						if(s2[(1<<n)-1][i][j]>s2[(1<<n)-1][r][j]){
							flag=0;
							break;
						}
				if(flag)
					r=i;
			}
	for(int i=1;i<=f[(1<<n)-1][r];i++)
		printf("%c",s2[(1<<n)-1][r][i]);
//	dfs((1<<n)-1,r);
//	printf("%d\n",ans);
	return 0;
}
2023/3/12 07:42
加载中...