HDU 4628 狀态壓縮

//又被題虐了MD

#include<stdio.h>

#include<string.h>

char ch[18];

int dis[(1<<17)],dp[(1<<17)];

int min(int a,int b)

{

if(a<b)return a;

return b;

}

int main()

{

int i,j,n,m;

while(scanf("%d",&n)!=EOF)

{

scanf("%s",ch);

int len=strlen(ch);

int cnt=(1<<len);

for(i=1;i<cnt;i++)

{

int l=0,r=len-1;

int tot=1;

while(l<r)

{

while(l<len&&!((1<<l)&i))

l++;

while(r>=0&&!((1<<r)&i))

r--;

if(ch[l]!=ch[r])

tot=0;

l++;

r--;

}

if(tot==0)

dis[i]=0;

else

dis[i]=1;

//printf("%d\n",dis[i]);

}

memset(dp,127,sizeof(dp));

dp[0]=0;

for(i=1;i<cnt;i++)

{

for(j=i;j>0;j=(i&(j-1)))

{

if(dis[j])

dp[i]=min(dp[i],dp[i-j]+1);

}

}

printf("%d\n",dp[cnt-1]);

}

}