这是一个大水题啊。。。
因为比赛时不会算复杂度耽误半天。
i从0到2^n枚举集合i的所有分割两半的情况的复杂度为O(3^n),可以想象这个过程相当于是给每个位标记0,1,2(0表示不选,1,2表示两个集合)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; char s[20];
int vis[1<<16]; int main(){
int t,T,i,j,len;
scanf("%d",&T);
for(t=1;t<=T;t++){
scanf("%s",s);
len=strlen(s);
for(i=1;i<(1<<len);i++){
bool flag=1;
int l=0,r=len-1;
while(l<r){
while(l<len && ((i&(1<<l))==0))
l++;
while(r>=0 && ((i&(1<<r))==0))
r--;
if(s[l]!=s[r]){
flag=0;
break;
}
l++,r--;
}
if(flag) vis[i]=1;
else vis[i]=len;
}
for(i=1;i<(1<<len);i++){
if(vis[i]==1)continue;
for(j=(i-1)&i;j;j=(j-1)&i) vis[i]=min(vis[i],vis[i-j]+vis[j]);
}
printf("%d\n",vis[(1<<len)-1]);
}
}
HDU 4628的更多相关文章
-
hdu 4628 Pieces
http://acm.hdu.edu.cn/showproblem.php?pid=4628 状态压缩DP 时间复杂度应该是 16*(2^32) 但是运行时要远小于这个数 所以加一定剪枝就可以过 代码 ...
-
hdu 4628(状态压缩)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4628 思路:首先把所有的回文找出来,如果当前状态为回文,则dp[state]=1,否则dp[state ...
-
HDU 4628 Pieces(DP + 状态压缩)
Pieces 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4628 题目大意:给定一个字符串s,如果子序列中有回文,可以一步删除掉它,求把整个序列删除 ...
-
HDU 4628 Pieces(状态压缩+记忆化搜索)
http://acm.hdu.edu.cn/showproblem.php?pid=4628 题意:给个字符窜,每步都可以删除一个字符窜,问最少用多少步可以删除一个字符窜分析:状态压缩+记忆化搜索 ...
-
[kmp+dp] hdu 4628 Pieces
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4622 Reincarnation Time Limit: 6000/3000 MS (Java/Ot ...
-
hdu 4628 动态规划
思路:首先就是状态压缩,然后判断哪些状态是回文串.最后就是动态方程:dp[i]=min(dp[i],dp[j]+1).这个方程得前提条件是状态(j-i)为回文串. #include<iostre ...
-
HDU 4628 多校第三场1008 dp
这题就没什么好说的了.直接枚举2 ^ 16 的状态,用1表示拿这位,0表示不拿,每次判断是否可以这么拿. #include <iostream> #include <cstdio&g ...
-
hdu 4628 Pieces 状压dp
题目链接 枚举所有状态, 1表示这个字符还在原来的串中, 0表示已经取出来了. 代码中j = (j+1)|i的用处是枚举所有包含i状态的状态. #include <iostream> #i ...
-
hdu 4628 Pieces 状态压缩dp
Pieces Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total S ...
随机推荐
-
tiny中文乱码问题,不过仅适用于windows,所以xml不可以出现中文
我是在SetAttribute() 函数之前使用的 SetAttribute(const char* name,const char * _value) 首先得到了一个CString 类型的变量 st ...
-
js网页换肤
使网页背景颜色可选黄/粉 <html> <head> <meta charset="utf-8"> <meta name="ge ...
-
[转载]各种在线api地址
J2SE1.7英文api地址: http://download.oracle.com/javase/7/docs/api/J2SE1.6英文api地址: http://download.oracle ...
-
.NET 单点登录
<appSettings> <!--是否启用单点登录接口--> <add key="IsStartCas" value="f ...
-
SCU-4437 Carries
https://blog.csdn.net/catglory/article/details/46539283 https://blog.csdn.net/u012127882/article/det ...
-
golang字符串拼接
四种拼接方案: 1,直接用 += 操作符, 直接将多个字符串拼接. 最直观的方法, 不过当数据量非常大时用这种拼接访求是非常低效的. 2,直接用 + 操作符,这个和+=其实一个意思了. 3,用字符串切 ...
-
Dom4j解析xml内容——(三)
Dom4j取标签中的内容用 getText ,取开始标签和结束标签之间的值. 取属性值有两种方式:
-
Intellij dea 注释行如何自动缩进?
Intellij dea 注释行如何自动缩进? 进入 Settings -> Code Style -> Java ,在右边选择 “Code Generation” Tab,然后找到 ...
-
06-python opencv 使用摄像头捕获视频并显示
https://blog.csdn.net/huanglu_thu13/article/details/52337013
-
主流品牌服务器(Dell、HP、IBM)远程管理卡IP配置参考
版权声明:个人网络收集整理,欢迎转载! https://blog.csdn.net/niufenger/article/details/80737878 ※Dell服务器iDRAC IP配置 ※HP服 ...