Pieces

2
aa
abb

1
2

对于每种字串状态i,枚举包含状态i的状态j(既i中有1的位置j也有)，然后判断状态j表示的字串消除的串i^j是否是回文串，是得话就可以从状态j到达状态i

对于如何枚举包含状态i的状态j:

for(int j=i;j<2^len;j=(j+1)|i);

比如:

i:1 1 0 1 0

j;1 1 0 1 0

则j+1:1 1 0 1然后(j+1)|i就将i中第一个为0的位置变为1

然后继续(j+1)|i其实就是在原前面已变位置的前提下，如果该位置前面还有0的就变成1，否则找下一个位置变为1

当然也可以枚举状态i的子状态:

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

枚举包含状态i的状态:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <iomanip>
#define INF 99999999
typedef long long LL;
using namespace std;

const int MAX=(1<<16)+10;
int len,bit;
int dp[MAX];
char s[20];
bool mark[MAX];

bool check(int x){
	if(x == 0)return true;
	int i=0,j=len-1;
	while(i<j){
		while(!(x&(1<<i)))++i;
		while(!(x&(1<<j)))--j;
		if(s[i] != s[j])return false;
		++i,--j;
	}
	return true;
}

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%s",s);
		len=strlen(s);
		bit=1<<len;
		dp[bit-1]=0;
		for(int i=0;i<bit;++i)mark[i]=check(i);
		for(int i=bit-2;i>=0;--i){
			dp[i]=INF;
			for(int j = i;j<bit;j=(j+1)|i){
				if(!mark[i^j])continue;
				if(dp[i]>dp[j]+1)dp[i]=dp[j]+1;
			}
		}
		printf("%d\n",dp[0]);
	}
	return 0;
}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <iomanip>
#define INF 99999999
typedef long long LL;
using namespace std;

const int MAX=(1<<16)+10;
int len,bit;
int dp[MAX];
char s[20];
bool mark[MAX];

bool check(int x){
	if(x == 0)return true;
	int i=0,j=len-1;
	while(i<j){
		while(!(x&(1<<i)))++i;
		while(!(x&(1<<j)))--j;
		if(s[i] != s[j])return false;
		++i,--j;
	}
	return true;
}

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%s",s);
		len=strlen(s);
		bit=1<<len;
		for(int i=0;i<bit;++i)mark[i]=check(i);
		for(int i=0;i<bit;++i)dp[i]=INF;
		dp[bit-1]=0;
		for(int i=bit-1;i>=0;--i){
			for(int j = i;j>0;j=((j-1)&i)){
				if(!mark[i^j])continue;
				if(dp[j]>dp[i]+1)dp[j]=dp[i]+1;
			}
			if(mark[i])if(dp[0]>dp[i]+1)dp[0]=dp[i]+1;
		}
		printf("%d\n",dp[0]);
	}
	return 0;
}

hdu4628之状态压缩dp,布布扣,bubuko.com

hdu4628之状态压缩dp

原文：http://blog.csdn.net/xingyeyongheng/article/details/21748679