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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1195】【Hnoi2006】【最短母串】  

2014-04-15 10:06:27|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:给出N个字符串,求最短的一个串包含这N个串。如果有多个最短的输出字典序最小的。
    
    wshjzaa君和咱讨论的问题0.0...比较ym他一直都坚持独立思考的特点。

    首先咱们去掉一些包含关系的串,然后咱们会发现,实际上答案就是这剩余的串排列在一起,然后相邻的进行压缩的结果。这里咱们来证明一下这个结论,实际上咱们考虑假设答案不是这样相邻的进行压缩的情况,但是咱们实际上可以找出每一个串出现的位置的起点,然后按这个起点排序,再把原来的串按这个顺序依次压缩的话,答案肯定就是那个,否则就不对了。这是用构造证明的。

    然后咱们的第一种方法就是暴力枚举摆放的顺序,然后依次压缩。
    这个方法显然需要优化,咱们考虑实际上枚举答案的时候,假设现在剩下的字符串咱们已经搜索过了,实际上可以直接调用以前的结果。也就是说咱们需要用记忆化来辅助,这样子想下去就像DP了。

    然后进一步想想,咱们实际上可以发现,实际上咱们不需要枚举顺序,只需要求出选择了某几个字符串来拼接的最小字符串即可,咱们可以用 12位二进制 来表示这 12个字符串,其中0表示没有选择,1表示选了,那么 f[i]代表的就是 选择了i的二进制中1的位上的字符串,所能得到的最短且字典序最小的字符串。
    然后转移就是枚举 那些为1的位,将它们变成0,再用那个状态来转移。比如 110可以用 100,010来转移。

    但是这里还是不对的,因为压缩可能对答案造成影响。假设咱们有一个最短串,但是和某个字符串并没有公共部分,而有一个次短串,它可以和这个字符串有公共部分, 然后这个次短串就占优势了。所以咱们还得加点限制,注意到这个压缩只和在最前面的字符串有关,所以咱们加一维表示最前面的那一个字符串是哪一个。

    这里咱们设f[i][j] 
    表示用 状态 j的字符串合成的最短串,且要求第i个字符串必须在开头

  (为什么必须开头?(其实咱一开始设计的时候是在尾部的),这个是后面才想清楚地....实际上咱那种也是可以的,但是不能保证开头的字典序233...这从开头加是为了确保最后扫描答案的时候能知道哪一个方案的字典序最小)

     那么咱们有转移方程:
     f[i][j] = max(f[k][w]+opt())
    其中k,w都是枚举的,然后 opt()是指的是 w状态下j缺少的那一个字符串的后缀和第k个字符串的最长前缀长度。

    用这个dp的话那么复杂度就是O(4^n*n^2),由于有很多不合法的状态,再加上位运算优化,对于12的还是可以过的。
    这个貌似大家记录的都是长度,再记录是由哪一个字符串转移来的,然后再最后去计算,实际上感觉还是直接记录字符串不是很幸福么 0.0(虽然最后还是用的长度...)

====================================

program bzoj1195; var a:array[0..13]of string; f,pre:array[0..13,0..1 shl 13-1]of longint; c:array[0..13,0..13]of longint; l:array[0..13]of longint; can:array[0..13]of boolean; n:longint; ans:ansistring; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; function spilt(s:string;len:longint;flag:boolean):string; var ans:string; i,j:longint; begin ans:=''; j:=length(s); if flag then for i:=j-len+1 to j do ans:=ans+s[i] else for i:=1 to len do ans:=ans+s[i]; exit(ans); end; function merge(u,v:longint):string; var ans:string; i:longint; begin ans:=''; for i:=1 to length(a[u])-c[u][v] do ans:=ans+a[u][i]; for i:=1 to length(a[v]) do ans:=ans+a[v][i]; exit(ans); end; function cmp(s1,s2:string):boolean; var len1,len2,i:longint; begin len1:=length(s1); len2:=length(s2); for i:=1 to min(len1,len2) do begin if s1[i]>s2[i] then exit(false); if s1[i]<s2[i] then exit(true); end; if len1<len2 then exit(true); exit(false); end; procedure init; var i,j,k,poss,mini,tmp:longint; begin readln(n); fillchar(f,sizeof(f),1); for i:=1 to n do readln(a[i]); fillchar(can,sizeof(can),true); for i:=1 to n do for j:=1 to n do if i<>j then if (pos(a[i],a[j])<>0) then if length(a[i])<length(a[j]) then can[i]:=false else if j>i then can[i]:=false; fillchar(c,sizeof(c),0); j:=0; for i:=1 to n do if can[i] then begin inc(j); a[j]:=a[i]; end; n:=j; for i:=1 to n do begin l[i]:=length(a[i]); f[i][1 shl (i-1)]:=l[i]; end; for i:=1 to n do for j:=1 to n do if i<>j then for k:=1 to min(l[i],l[j]) do if spilt(a[i],k,true)=spilt(a[j],k,false) then c[i][j]:=k; fillchar(pre,sizeof(pre),0); for i:=0 to (1 shl n)-1 do for j:=1 to n do if i and (1 shl (j-1))=1 shl (j-1) then for k:=1 to n do if (k<>j)and(i and (1 shl (k-1))=1 shl (k-1))then if (f[j][i]>f[k][i-(1 shl (j-1))]+l[j]-c[j][k]) or ((f[j][i]=f[k][i-(1 shl (j-1))]+l[j]-c[j][k]) and(f[j][i]<>16843009))then begin if f[j][i]>f[k][i-(1 shl (j-1))]+l[j]-c[j][k] then begin f[j][i]:=f[k][i-(1 shl (j-1))]+l[j]-c[j][k]; pre[j][i]:=k; end else if cmp(merge(j,k),merge(j,pre[j][i])) then pre[j][i]:=k; end; mini:=maxlongint; poss:=0; for i:=1 to n do if f[i][(1 shl n)-1]<=mini then begin if mini>f[i][(1 shl n)-1] then begin mini:=f[i][(1 shl n)-1]; poss:=i; end else if cmp(a[i],a[poss]) then poss:=i; end; ans:=''; i:=(1 shl n)-1; for j:=1 to n do begin if pre[poss][i]<>0 then ans:=ans+spilt(a[poss],l[poss]-c[poss][pre[poss][i]],false) else ans:=ans+a[poss]; tmp:=i; i:=i-(1 shl (poss-1)); poss:=pre[poss][tmp]; end; write(ans); end; begin init; end.
  评论这张
 
阅读(163)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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