|
这题就没什么好说的了。直接枚举2 ^ 16 的状态，用1表示拿这位，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 ;
} |