这题就没什么好说的了。直接枚举2 ^ 16 的状态，用1表示拿这位，0表示不拿，每次判断是否可以这么拿。

[cpp] view plaincopyprint
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

inline void RD(int &ret) {
char c;
do {
c = getchar();
} while(c < '0' || c > '9') ;
ret = c - '0';
while((c=getchar()) >= '0' && c <= '9')
ret = ret * 10 + ( c - '0' );
}
inline void OT(int a) {
if(a >= 10)OT(a / 10) ;
putchar(a % 10 + '0') ;
}
int is[20] ;
int MV[1 << 17] ;
int dp[1 << 17] ;
char a[20] ;
int main() {
int t ;
cin >> t ;
while( t -- ) {
cin >> a ;
int l = strlen(a) ;
dp[0] = 0 ;
for (int i = 1 ; i < (1 << l ) ; i ++ ){
int aa = i ;
int num = 0 ;
for (int j = 0 ; j < l ; j ++ ){
if((aa >> j) & 1){
is[num ++ ] = (int)a[j] ;
}
}
bool flag = 0 ;
for (int j = 0 ; j < num / 2 ; j ++ ){
if(is[j] != is[num - j - 1]){
flag = 1 ;
break ;
}
}
if(!flag)MV[i] = 1 ;
else MV[i] = 0 ;
}
for (int i = 1 ; i < (1 << l) ; i ++ ){
if(MV[i])dp[i] = dp[0] + 1 ;
else dp[i] = inf ;
for (int j = i ; j > 0 ; -- j &= i){//这个操作是看标程的，一开始我在这里T了几发。
if(MV[j]){
dp[i] = min(dp[i] , dp[i - j] + 1) ;
}
}
}
cout << dp[(1 << l ) - 1] << endl;
}
return 0 ;
}