字符串长度只有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;
}
分享到:
相关推荐
HDU的一题........HDU DP动态规
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
上面可能有poj的题目,hdu的题目,spoj的题目,sgu的题目,hust上的题目,fzu上的题目
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
动态规划DP题解 POJ HDU部分动态规划DP题解
hdu 1200 字符串处理。 将本来的字符串回旋摆放 再从上到下输出 我们就找到规律。每2*n是一个循环,然后对每个2*n内的第i和2*n-i-1输出就好了
hdu 1005.比较简单的一道题,有兴趣的可以看看。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
lazycal的集训队报告:初探数位DP 以HDU 2089,HDU 3652, URAL 1057等题目为例,介绍了数位DP的算法
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧