UVA 10716 Evil Straw Warts Live 回文数贪心

题意：给出一串字符串，每次交换相邻的两个字符，求到达回文串的最少交换次数。

每次找最外面的两个字母，如果相同就向内缩进判断，如果不同，就找到里面能够让两边相同的最近的字符，进行交换，然后向内缩进判断。

调了挺久，以后一定要把算法搞清楚再敲。。。

代码：


 /* 
 *   Author:        illuz  
 *   Blog:          http://blog.csdn.net/hcbbt 
 *   File:          uva10716.cpp 
 *   Lauguage:      C/C++ 
 *   Create Date:   2013-09-03 23:03:20 
 *   Descripton:    UVA 10716 Evil Straw Warts Live, greed 
 */  
#include   
#include   
#define rep(i, n) for (int i = 0; i < (n); i++)  
#define swap(a, b) {int t = a; a = b; b = t;}  
#define mc(a) memset(a, 0, sizeof(a))  
  
const int MAXN = 110;  
int n, len, app[26], cnt;  
char s[MAXN];  
  
void solve(char* a, int l) {  
    if (a[0] == a[l - 1]) return;  
    for (int i = 1; i < l - 1; i++)  
        if (a[i] == a[l - 1]) {  
            for (int j = i; j >




 0; j--)  
                swap(a[j], a[j - 1]);  
            cnt += i;  
            return;  
        }  
        else if (a[l - i - 1] == a[0]) {  
            for (int j = l - i - 1; j < l - 1; j++)  
                swap(a[j], a[j + 1]);  
            cnt += i;  
            return;  
        }  
}  
  
int main() {  
    scanf("%d", &n);  
    while (n--) {  
        scanf("%s", s);  
        len = strlen(s);  
        mc(app);  
        rep(i, len) app[s[i] - 'a']++;  
        cnt = 0;  
        rep(i, 26) if (app[i] % 2) cnt++;  
        if (cnt > 1)  
            printf("Impossible\n");  
        else {  
            cnt = 0;  
            rep(i, len / 2)   
                solve(s + i, len - 2 * i);  
            printf("%d\n", cnt);  
        }  
    }  
    return 0;  
}

UVA 10716 Evil Straw Warts Live 回文数 贪心