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

ydc的博客

 
 
 

日志

 
 

bzoj 1195(hnoi2006) 最短母串  

2013-03-27 23:40:47|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这是我暑假准备联赛时做过的原题,来自POJ上的,然后这次就直接贴代码了……
当时我还是写的C呢……而代码风格也和现在截然不同啊
讲讲方法吧
首先去掉包含关系
然后就是裸的状压DP了
不过这次F[i][S](S是二进制状态)必须得定义i是前缀
把1~n个串中除了第i个串以外的串接在第i个串后面能得到n-1个串,我们预处理一个数组rank[i][j]表示j串接在i串后面是这n-1个串中字典序排第几的
转移的时候,不仅记录F[i][j],还记录father[i][j]表示F[i][j]是由(father[i][j],j^(1<<(father[i][j]-1)))这个状态推过来的(不要被吓到了就是由哪个状态推过来的)
对于一个新的解p,它是由i放在前缀接在k前面的情况下,转移如下:
若father=-1,p来更新F,i更新father
若p优于当前F,同上
若p与当前F一样优,且当前枚举的串k接在i后面比当前枚举串k接在father后面更优(可用预处理的那个数组O(1)判断),同上
最后倒着输出


#include<stdio.h>
#include<string.h>
struct str
{
char letter[1600];
int len;
}ans,a[20];
struct
{
struct str temp;
int x,y;
}add[500];
int f[1<<12][15],father[1<<12][15],reduce[20][20],cost[20][20],n,m,max,Test,s;
struct str ADD(struct str ans,int k,int reduce)
{
int i;
for(i=ans.len;i<ans.len+a[k].len-reduce;i++)
ans.letter[i]=a[k].letter[reduce+i-ans.len];
ans.letter[i]=0;
ans.len=ans.len+a[k].len-reduce;
return ans;
}
void quick(int l,int r)
{
int i=l,j=r;
struct str x=add[(i+j)>>1].temp;
while(i<=j)
{
while(strcmp(add[i].temp.letter,x.letter)<0) i++;
while(strcmp(add[j].temp.letter,x.letter)>0) j--;
if(i<=j)
{
add[0]=add[i],add[i]=add[j],add[j]=add[0];
i++,j--;
}
}
if(i<r) quick(i,r);
if(j>l) quick(l,j);
}
void READY()
{
int i,j,k,r;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=0;k<a[i].len;k++)
{
for(r=0;k+r<a[i].len&&a[i].letter[k+r]==a[j].letter[r];r++);
if(k+r==a[i].len)
{
reduce[j][i]=r;
break;
}
}
s=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
s++;
add[s].temp=ADD(a[i],j,reduce[j][i]),add[s].x=i,add[s].y=j;
}
quick(1,s);
for(i=1;i<=s;i++)
cost[add[i].x][add[i].y]=i;
}
void read()
{
int i,j,k,r;
scanf("%d",&n);
memset(reduce,0,sizeof(reduce));
for(i=1;i<=n;i++)
{
scanf("%s",a[i].letter);
a[i].len=strlen(a[i].letter);
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i==j) continue;
for(k=0;k<a[j].len;k++)
{
for(r=0;r+k<a[j].len&&r<a[i].len&&a[j].letter[k+r]==a[i].letter[r];r++);
if(r==a[i].len) break;
}
if(k<a[j].len) a[i].letter[0]=0;
}
for(i=n;i>=1;i--)
if(a[i].letter[0]==0)
{
for(j=i;j<n;j++)
a[j]=a[j+1];
n--;
}
m=(1<<n)-1;
}
void DP()
{
int i,j,k;
for(i=0;i<=m;i++)
for(j=1;j<=n;j++)
f[i][j]=father[i][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
int add=1<<(j-1);
if((i&add)==0)
for(k=1;k<=n;k++)
if((i&(1<<(k-1)))!=0)
{
if(father[i+add][j]==0)
{
f[i+add][j]=f[i][k]+reduce[k][j],father[i+add][j]=k;
continue;
}
if(f[i+add][j]<f[i][k]+reduce[k][j])
f[i+add][j]=f[i][k]+reduce[k][j],father[i+add][j]=k;
else if(f[i+add][j]==f[i][k]+reduce[k][j]&&cost[j][father[i+add][j]]>cost[j][k])
father[i+add][j]=k;
}
}
}
void solve()
{
max=-1;
int i,j,now;
for(i=1;i<=n;i++)
{
if(max<f[m][i])
{
max=f[m][i],now=m;
ans=a[i];
for(j=i;father[now][j]!=0;)
{
ans=ADD(ans,father[now][j],reduce[father[now][j]][j]);
int t=j;
j=father[now][j],now-=(1<<(t-1));
}
}
else if(max==f[m][i])
{
struct str temp=a[i];
now=m;
for(j=i;father[now][j]!=0;)
{
temp=ADD(temp,father[now][j],reduce[father[now][j]][j]);
int t=j;
j=father[now][j],now-=(1<<(t-1));
}
if(strcmp(ans.letter,temp.letter)>0) ans=temp;
}
}
}
int main()
{
read();
READY();
DP();
solve();
printf("%s\n",ans.letter);
return 0;
}
  评论这张
 
阅读(936)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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