1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <cctype> #define INF 2000000000 using namespace std; typedef long long ll; int (){ int f = 1, x = 0; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); } while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar(); return f * x; } char s[1005]; bool mat[50][50], vis[50]; int p[10], n, b[10], ansp[10]; void init(){ memset(mat, 0, sizeof(mat)); memset(vis, 0, sizeof(vis)); for(int i = 0; isalpha(s[i]); ++i){ int cur = s[i++] - 'A'; vis[cur] = 1; for(i++; isalpha(s[i]); ++i){ int to = s[i] - 'A'; mat[cur][to] = mat[to][cur] = 1; vis[to] = 1; } } } void solve(){ n = 0; for(int i = 0; i < 26; ++i) if(vis[i]) p[n++] = i; int ans = INF; do{ int cur = 0; memset(b, 0, sizeof(b)); for(int i = 0; i < n; ++i){ for(int j = i - 1; j >= 0; --j) if(mat[p[i]][p[j]]) b[i] = max(b[i], i - j); for(int j = i + 1; j < n; ++j) if(mat[p[i]][p[j]]) b[i] = max(b[i], j - i); cur = max(cur, b[i]); if(cur >= ans) break; } if(cur < ans){ memcpy(ansp, p, sizeof(p)); ans = cur; } }while(next_permutation(p, p + n)); for(int i = 0; i < n; ++i) printf("%c ", ansp[i] + 'A'); printf("-> %dn", ans); } int main(){ for(; ; ){ scanf("%s", s); if(s[0] == '#')break; init(); solve(); memset(s, 0, sizeof(s)); } return 0; }
|
近期评论