這題就沒什麼好說的了。直接枚舉2 ^ 16 的狀態，用1表示拿這位，0表示不拿，每次判斷是否可以這麼拿。
[cpp] view plaincopyprint?
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 2000000000
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;
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 ;
}
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 2000000000
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;
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 ;
}
