HDU 4628

时间:2021-10-23 21:41:43

这是一个大水题啊。。。

因为比赛时不会算复杂度耽误半天。

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的更多相关文章

  1. hdu 4628 Pieces

    http://acm.hdu.edu.cn/showproblem.php?pid=4628 状态压缩DP 时间复杂度应该是 16*(2^32) 但是运行时要远小于这个数 所以加一定剪枝就可以过 代码 ...

  2. hdu 4628&lpar;状态压缩&rpar;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4628 思路:首先把所有的回文找出来,如果当前状态为回文,则dp[state]=1,否则dp[state ...

  3. HDU 4628 Pieces(DP &plus; 状态压缩)

    Pieces 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4628 题目大意:给定一个字符串s,如果子序列中有回文,可以一步删除掉它,求把整个序列删除 ...

  4. HDU 4628 Pieces(状态压缩&plus;记忆化搜索)

    http://acm.hdu.edu.cn/showproblem.php?pid=4628 题意:给个字符窜,每步都可以删除一个字符窜,问最少用多少步可以删除一个字符窜分析:状态压缩+记忆化搜索  ...

  5. &lbrack;kmp&plus;dp&rsqb; hdu 4628 Pieces

    题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4622 Reincarnation Time Limit: 6000/3000 MS (Java/Ot ...

  6. hdu 4628 动态规划

    思路:首先就是状态压缩,然后判断哪些状态是回文串.最后就是动态方程:dp[i]=min(dp[i],dp[j]+1).这个方程得前提条件是状态(j-i)为回文串. #include<iostre ...

  7. HDU 4628 多校第三场1008 dp

    这题就没什么好说的了.直接枚举2 ^ 16 的状态,用1表示拿这位,0表示不拿,每次判断是否可以这么拿. #include <iostream> #include <cstdio&g ...

  8. hdu 4628 Pieces 状压dp

    题目链接 枚举所有状态, 1表示这个字符还在原来的串中, 0表示已经取出来了. 代码中j = (j+1)|i的用处是枚举所有包含i状态的状态. #include <iostream> #i ...

  9. hdu 4628 Pieces 状态压缩dp

    Pieces Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total S ...

随机推荐

  1. tiny中文乱码问题,不过仅适用于windows,所以xml不可以出现中文

    我是在SetAttribute() 函数之前使用的 SetAttribute(const char* name,const char * _value) 首先得到了一个CString 类型的变量 st ...

  2. js网页换肤

    使网页背景颜色可选黄/粉 <html> <head> <meta charset="utf-8"> <meta name="ge ...

  3. &lbrack;转载&rsqb;各种在线api地址

    J2SE1.7英文api地址: http://download.oracle.com/javase/7/docs/api/J2SE1.6英文api地址:  http://download.oracle ...

  4. &period;NET 单点登录

    <appSettings>     <!--是否启用单点登录接口-->     <add key="IsStartCas" value="f ...

  5. SCU-4437 Carries

    https://blog.csdn.net/catglory/article/details/46539283 https://blog.csdn.net/u012127882/article/det ...

  6. golang字符串拼接

    四种拼接方案: 1,直接用 += 操作符, 直接将多个字符串拼接. 最直观的方法, 不过当数据量非常大时用这种拼接访求是非常低效的. 2,直接用 + 操作符,这个和+=其实一个意思了. 3,用字符串切 ...

  7. Dom4j解析xml内容——(三)

    Dom4j取标签中的内容用 getText ,取开始标签和结束标签之间的值. 取属性值有两种方式:

  8. Intellij dea 注释行如何自动缩进&quest;

    Intellij dea 注释行如何自动缩进?   进入 Settings -> Code Style -> Java ,在右边选择 “Code Generation” Tab,然后找到 ...

  9. 06-python opencv 使用摄像头捕获视频并显示

    https://blog.csdn.net/huanglu_thu13/article/details/52337013

  10. 主流品牌服务器(Dell、HP、IBM)远程管理卡IP配置参考

    版权声明:个人网络收集整理,欢迎转载! https://blog.csdn.net/niufenger/article/details/80737878 ※Dell服务器iDRAC IP配置 ※HP服 ...