2015
09-17

# Pieces

You heart broke into pieces.My string broke into pieces.But you will recover one day,and my string will never go back.
Given a string s.We can erase a subsequence of it if this subsequence is palindrome in one step. We should take as few steps as possible to erase the whole sequence.How many steps do we need?
For example, we can erase abcba from axbyczbea and get xyze in one step.

The first line contains integer T,denote the number of the test cases. Then T lines follows,each line contains the string s (1<= length of s <= 16).
T<=10.

The first line contains integer T,denote the number of the test cases. Then T lines follows,each line contains the string s (1<= length of s <= 16).
T<=10.

2
aa
abb

1
2

f[i]表示状态i最少几次可以全删完， 初始化f数组INF

f[i] = min{f[i], f[s]+1 } s是i的子集。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;

typedef long long int64;
const int INF = 0x3f3f3f3f;
const int MAXN = (1<<16)+10;

char str[20];
bool check[MAXN];
int f[MAXN];
int maxSta;

bool isPalind(int st, int len){
char sub[20];
int idx = 0;
for(int i=0; i<len; ++i){
if( (st>>i)&1 )
sub[idx++] = str[i];
}
for(int i=0; i<idx/2; ++i){
if(sub[i] != sub[idx-1-i])
return false;
}
return true;
}

int main(){

int T;
scanf("%d", &T);
check[0] = false;
while(T--){

scanf("%s", str);
int len = strlen(str);
maxSta = (1<<len)-1;
for(int i=1; i<=maxSta; ++i){
check[i] = isPalind(i, len);
}

memset(f, 0x7f, sizeof(f));
f[0] = 0;
for(int i=1; i<=maxSta; ++i){
for(int s=i; s; s=(s-1)&i)
if(check[s])
f[i] = min(f[i], f[i^s]+1);
}
printf("%d\n", f[maxSta]);

}
return 0;
}

1. 原单批发 JEEP(吉普)Paul Homme(大嘴猴)Victoria Beckham(维多利亚·贝克汉姆)Lindsay phillips幸福狐狸xuanmeigui(炫玫瑰)ECCO(爱步)Wei信:LoveMeJck