60pts 球调/球叉
查看原帖
60pts 球调/球叉
641829
sstitch楼主2024/9/10 20:15
#include<bits/stdc++.h>
using namespace std;
const int N = 15, M = 10000;
int dp[M][N], n, l[N];
string ans[M][N];
string s[N];
bool rev(string a, string b) {
	reverse(a.begin(), a.end());
	return a == b;
}
int len(string a, string b) {
	int x = a.length(), y = b.length(); 
	int i = x - 1, j = 0, ans = 0, cnt = 0;
	string str1 = "", str2 = "";
	while(i >= 0 && j < y) {
		str1 = str1 + a[i];
		str2 = str2 + b[j];
		cnt++;
		if(rev(str1, str2)) {
			ans = cnt;
		}
		i--; j++;
	}
	return ans;
}
int main() {
//	cout << len("ABCD", "BCDABC") << '\n';
	ios::sync_with_stdio(0);
	cin >> n; int sum = 0;
	for(int i = 0; i < n; i++) cin >> s[i], l[i] = s[i].length(), sum += l[i];
	for(int i = 0; i < n; i++) {
		dp[1 << i][i] = 0;
		ans[1 << i][i] = s[i];
	}
	for(int i = 0; i < (1 << n); i++) {
		for(int j = 0; j < n; j++) if(i & (1 << j)) {
			for(int k = 0; k < n; k++) if(i & (1 << k) && k != j) {
				int lst = i - (1 << j), L = len(s[k], s[j]);
				if(dp[i][j] <= dp[lst][k] + L) {
					dp[i][j] = dp[lst][k] + L;
					ans[i][j] = ans[lst][k];
					for(int o = L; o < l[j]; o++) {
						ans[i][j] += s[j][o];
					}
		//			cout << i << ' ' << j << ' ' << lst << ' ' << k << ans[i][j] << ' ' << dp[i][j] << '\n';
				}
			}
		}
	}
	int mx = 0; string res = "";
	for(int i = 0; i < n; i++) {
		if(mx < dp[(1 << n) - 1][i]) {
			mx = dp[(1 << n) - 1][i];
			res = ans[(1 << n) - 1][i];
		}
        if(mx == dp[(1 << n) - 1][i] && ans[(1 << n) - 1][i] < res) {
            res = ans[(1 << n) - 1][i];
        }
	}
	cout << res;
	return 0;
}
2024/9/10 20:15
加载中...