求条WA #1
查看原帖
求条WA #1
531731
playerqwq楼主2025/1/18 10:12
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a;i <= b;++i)
#define per(i,a,b) for(int i = b;i >= a;--i)
typedef long long ll;
const ll Mod = 1e9+9;
inline ll read(){
    ll x = 0,f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')x = x * 10 + ch - '0',ch = getchar();
    return x * f;
}
void write(ll x){
    if(x < 0)putchar('-'),x = -x;
    if(x > 9)write(x / 10);
    putchar(x % 10 + '0');
    return;
}
ll dis[15][15],dp[15][8192],n,le[15],cnt;// dis[a][b] b在a后面的重合部分长度 
string Ans[15][8192],s[15],q,res[15];
int main(){
	memset(dp,0x3f,sizeof(dp));
	n = read();
	rep(i,1,n)cin >> s[i],le[i] = s[i].size();
	rep(i,1,n){
		rep(j,1,n){
			if(i == j)continue;
			rep(k,1,min(le[i],le[j])){
				bool fl = 0;
				rep(f,1,k){
					if(s[i][le[i] - k + f - 1] != s[j][f - 1]){
						fl = 1;
						break;
					}
				}
				if(!fl)dis[i][j] = k;
			}
		}
		dis[0][i] = 0;
		dp[i][(1 << (i - 1))] = le[i];
		Ans[i][(1 << (i - 1))] = s[i];
	}
	rep(i,0,(1 << n) - 1){
		rep(j,1,n){
			if((1 << (j - 1)) & i){
				rep(k,1,n){
					if(!((1 << (k - 1)) & i)){
//						cout << k << " " << (i | (1 << (k - 1))) << " from " << j << " " << i << endl;
						if(dp[k][i | (1 << (k - 1))] > dp[j][i] + le[k] - dis[j][k]){
							dp[k][i | (1 << (k - 1))] = dp[j][i] + le[k] - dis[j][k];
							Ans[k][i | (1 << (k - 1))] = Ans[j][i];
							rep(f,dis[j][k] + 1,le[k])Ans[k][i | (1 << (k - 1))] += s[k][f - 1];
						}
						else if(dp[k][i | (1 << (k - 1))] == dp[j][i] + le[k] - dis[j][k]){
							q = Ans[j][i];
							rep(f,dis[j][k] + 1,le[k])q += s[k][f - 1];
							if(q < Ans[k][i | (1 << (k - 1))])Ans[k][i | (1 << (k - 1))] = q;
						}
					}
				}
			}
		}
	}
	ll mx = 1e18;
	rep(i,1,n){
//		cout << mx << endl;
		if(mx > dp[i][(1 << n) - 1])mx = dp[i][(1 << n) - 1],cnt = 1,res[cnt] = Ans[i][(1 << n) - 1];
		else if(mx == dp[i][(1 << n) - 1])res[++cnt] = Ans[i][(1 << n) - 1];
	}
	sort(res + 1,res + cnt + 1);
	cout << res[1] << endl;
	return 0;
}

2025/1/18 10:12
加载中...