poj 1854 贪心。。。(把一个字符串改成回文串的最小操作数)

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int main() { int T,count[27]; char str[8888]; scanf("%d",&T); while(T--) { int res=0,cnt=0; memset(count,0,sizeof(count)); scanf("%s",str); int len=strlen(str); for(int i=0;i<len;i++) { count[str[i]-'a']++; } for(int i=0;i<26;i++) { if(count[i]&1) cnt++; } if(cnt>1) printf("Impossible\n"); else { int lo1,lo2; for(int i=0,j=len-1;i<j;i++,j--) { if(str[i]==str[j]) continue; for(int k=j;k>=i;k--) { if(k!=i&&str[k]==str[i]) { lo1=k; break; } lo1=k; } for(int k=i;k<=j;k++) { if(k!=j&&str[k]==str[j]) { lo2=k; break; } lo2=k; } if((j-lo1)>(lo2-i)) { res+=lo2-i; for(int k=lo2;k>i;k--) swap(str[k],str[k-1]); } else { res+=j-lo1; for(int k=lo1;k<j;k++) swap(str[k],str[k+1]); } } printf("%d\n",res); } } }