注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

 
 
 

日志

 
 

HNOI 2006 day1 最短母串 ( bzoj 1191 ) 状压DP  

2014-04-16 07:36:13|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
表示状压DP的题在众多算法中 暴力分属于给得极多的 所以长期考试时即使看出状压DP也不写 打好暴力就去想其他的题了 然后如今见了状压DP就有一丝阴影 于是决定把此题改好
-------------------------------------------------------------------------------------------
第一遍写 由于思路清晰 很快就写好了 中途一次调试都没有——然后也就没有保存。。。。。。
于是又重写一遍 发现居然是 O(2^n*n^2*L^2)的复杂度(L在最坏情况下=nm 也就是600.。。)
于是结果就和暴力没多大差异了 然后忽然发现是因为没有预处理。。。。
记得noip的时候就没写过预处理 wc也是 但是似乎如果写了的话 就可以多拿些分了。。。
于是就开始写预处理了 表示一开始考虑过这个问题
如果 A+B+C(+代表压缩后的链接) C不仅可以把B完全覆盖 而且还可以与A有重合部分怎么办。。。。
结果发现完全是自己想多了 因为还有一个状态A+C+B可以达到更优 所以就不用担心被这种情况给坑掉
然后这样复杂度就是 O(2^n*n^2*L+n^2*m^2)=O(2^n*n^2*L)=O(2^n*n^3*m)
差不多是3*10^8 ( 不过这是比较松的上界 没有TLE也是正常的 )
内存有些卡着过(4000*12*600)据说记录下是由哪个状态更新的,
而不把当前状态的串完全记录下来会好些?(这种做法
-------------------------------------------------------------------------------------------
顺遍表示 对于C党
如果是比较不相同长度的字符串字典序大小的话 还是用strncmp而不要用strcmp了
不然有可能会出现些奇怪的情况。。。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define rep(i,n) for(int i=1;i<=n;++i)
#define imax(x,y) (x>y?x:y)
#define imin(x,y) (x<y?x:y)
using namespace std;
const int A=4100,N=13,L=610;
char ans[A][N][L],tch[A];
int len[A][N],lens[N][N];
int n,all,lt,num=0;
bool check(int aa,int a2,int bb,int b2,int k)
{
for(int i=0;i+k<len[aa][a2];++i)
if(ans[bb][b2][i]!=ans[aa][a2][i+k])return 0;
return 1;
}
void mergechar(int aa,int a2,int bb,int b2,int cc)
{
lt=len[aa][a2]+len[bb][b2]-lens[a2][b2];
int lala=len[aa][a2],lblb=len[bb][b2];
if(lt<len[cc][b2])
{
for(int i=0;i<lala;++i)
ans[cc][b2][i]=ans[aa][a2][i];
for(int i=lala;i<lt;++i)
ans[cc][b2][i]=ans[bb][b2][lblb-lt+i];
len[cc][b2]=lt;
ans[cc][b2][lt]='\0';
}
else if(lt==len[cc][b2])
{
for(int i=0;i<lala;++i)
tch[i]=ans[aa][a2][i];
for(int i=lala;i<lt;++i)
tch[i]=ans[bb][b2][lblb-lt+i];
if(strcmp(ans[cc][b2],tch)>0)
{
for(int i=0;i<lala;++i)
ans[cc][b2][i]=ans[aa][a2][i];
for(int i=lala;i<lt;++i)
ans[cc][b2][i]=ans[bb][b2][lblb-lt+i];
len[cc][b2]=lt;
ans[cc][b2][lt]='\0';
}

}
}
int main()
{
scanf("%d",&n);
all=(1<<n)-1;
memset(len,60,sizeof(len));
rep(i,all)
{
if(i==(i&-i))
{
++num;
scanf("%s",ans[i][num]);
len[i][num]=strlen(ans[i][num]);
for(int j=1,j2=1;j<i;j<<=1,++j2)
{
for(int k=0;k<=len[i][num];++k)
if(check(i,num,j,j2,k))
{
lens[num][j2]=len[i][num]-k;
break;
}
for(int k=0;k<=len[j][j2];++k)
if(check(j,j2,i,num,k))
{
lens[j2][num]=len[j][j2]-k;
break;
}
}
}
else
{
for(int j=1,j2=1;j<i;j<<=1,++j2)
if((j|i)==i)
{
int k=i-j;
for(int k2=1;k2<=num;++k2)
if((1<<(k2-1))&k)
mergechar(k,k2,j,j2,i);
}
}
}
int lans=610,pos;
rep(i,n)
if(len[all][i]<lans)
{
lans=len[all][i];
pos=i;
}
rep(i,n)
if(len[all][i]==lans&&i!=pos&&strcmp(ans[all][pos],ans[all][i])>0)pos=i;
printf("%s",ans[all][pos]);
//printf("\n%d",len[all][pos]);
return 0;
}



  评论这张
 
阅读(145)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017