`
844604778
  • 浏览: 544944 次
文章分类
社区版块
存档分类
最新评论

hdu 4628 字符串状压dp

 
阅读更多

字符串长度只有16位,可以用状态压缩保存删除字符串的情况,比如 abeca 10101就代表删除aea字符串

首先枚举1~(1<<n)-1,所有情况,判断每种情况是否是回文串,用数组记录。

然后就是状态压缩dp,对于状态 i 可以用 for(int j=i;j>0;j=(j-1)&i) 来枚举i状态的所有子集

dp[i]= min(dp[i-j]+1,dp[i]) i-j状态必须是回文串


#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
char s[20];
int st[1<<16];
int dp[1<<16];
bool isok(int n,int l)
{
vector<char> v;
int pos=l-1;
while(n)
{
if(n&1) v.push_back(s[pos]);
n>>=1;
pos--;
}
int len=v.size();
for(int i=0;i<len/2;i++)
{
if(v[i]!=v[len-i-1]) return false;
}
return true;
}
int main()
{
int cas;
cin>>cas;
while(cas--)
{
scanf("%s",s);
int n;
n=strlen(s);
int top=(1<<n);
memset(st,0,sizeof(st));
for(int i=1;i<top;i++)
{
if(isok(i,n)) dp[i]=st[i]=1;
else dp[i]=inf;
}
for(int i=1;i<top;i++)
{
for(int j=i;j>0;j=((j-1)&i))
{
if(st[j])
{
dp[i]=min(dp[i],dp[i-j]+1);
}
}
}
cout<<dp[top-1]<<endl;
}
return 0;
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics