本文主要是介绍uva 10716 Evil Straw Warts Live，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：求最少的步骤使得原串变为回文串，贪心的做法很容易想到：每次都找离两端距离和最近的一对字符，然后分别移到两端就行了
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 8005;char str[MAXN];
int vis[MAXN];void swap(int &a,int &b)
{int t = a;a = b;b = t;
}bool isok()
{memset(vis,0,sizeof(vis));for (int i = 0; str[i]; i++)vis[str[i] - 'a']++;int sum = 0;for (int i = 0; i < 26; i++)if (vis[i] % 2){sum++;if (sum > 1)return false;}return true;
}int solve()
{int len = strlen(str),sum = 0;int left = 0,right = len - 1;while (left < right){int first = left,last = right,Max = MAXN *2;memset(vis,0,sizeof(vis));for (int i = left; i < right; i++){if (!vis[i]){vis[i] = true;int lastOccur = i,j;for (j = i + 1; j <= right; j++)if (str[j] == str[i]){vis[j] = true; // 中间的就更不可能是这个字符的最短了lastOccur = j;}if (i - left + right - lastOccur < Max){first = i,last = lastOccur;Max = i - left + right - lastOccur;}}}for (int i = first; i > left; i--){swap(str[i],str[i-1]);sum++;}for (int i = last; i < right; i++){swap(str[i],str[i+1]);sum++;}left++,right--;}return sum;
}int main()
{int t;scanf("%d",&t);while (t--){scanf("%s",str);if (isok())printf("%d\n",solve());else printf("Impossible\n");}return 0;
}这篇关于uva 10716 Evil Straw Warts Live的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
