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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SGU327 神状压  

2012-08-17 21:21:06|  分类: SGU300系列 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
感觉近两天状态下降很快,自从做了那场CF后整个人都没精神掉了
本题极神,yy的题解上表示他不会做
看金斌的题解时看了半天,加上机房没电,完全处于一种无所事事的状态
不过本题一遍AC,感觉还是蛮不错的

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;

const int NUM=15;
const int MAX=1<<15;
const int MAXL=30+1;
const int INF=1000000000;

int n,f[MAX][NUM][2],comeT[MAX][NUM][2],comeI[MAX][NUM][2],comeK[MAX][NUM][2];
string a[NUM],temp[NUM];
int delta[NUM][2][NUM][2];

string rev(string a)
{
reverse(a.begin(),a.end());
return a;
}

string match(string a,string b)
{
size_t i;
for(i=0;i<a.size();++i)
if(a.substr(i,a.size()-i) == b.substr(0,a.size()-i))
return a+b.substr(a.size()-i,b.size()-(a.size()-i));
return a+b;
}

string get(int now,int np,int k)
{
if(!comeT[now][np][k])
{
if(!k)return match(a[np],rev(a[np]));
else return match(rev(a[np]),a[np]);
}else
{
string b=get(comeT[now][np][k],comeI[now][np][k],comeK[now][np][k]);
string c=a[np];
if(k)c=rev(c);
int j=match(c,b).size()-b.size();
return match(c,b)+rev(c).substr(c.size()-j,j);
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i,j,k,T,np,l,o,nw;
cin>>n;
for(i=1;i<=n;++i)cin>>a[i];
int top=0,flag=1;
for(i=1;i<=n;++i)
{
for(flag=1,j=1;j<=top;++j)if(a[i]==temp[j] || a[i]==rev(temp[j]))flag=0;
if(flag)temp[++top]=a[i];
}
for(n=top,top=0,i=1;i<=n;++i)a[i]=temp[i];
for(i=1;i<=n;++i)
{
for(flag=1,j=1;j<=n;++j)
if(i!=j && ( a[j].find(a[i])!=string::npos || rev(a[j]).find(a[i])!=string::npos ) )
flag=0;
if(flag)temp[++top]=a[i];
}
for(n=top,i=1;i<=n;++i)a[i-1]=temp[i];
for(i=0;i<n;++i)
for(j=0;j<n;++j)
{
delta[i][0][j][0]=match(a[i],a[j]).size()-a[i].size();
delta[i][0][j][1]=match(a[i],rev(a[j])).size()-a[i].size();
delta[i][1][j][0]=match(rev(a[i]),a[j]).size()-a[i].size();
delta[i][1][j][1]=match(rev(a[i]),rev(a[j])).size()-a[i].size();
}
for(i=0;i<n;++i)
for(k=0;k<2;++k)
f[1<<i][i][k]=a[i].size()+delta[i][k][i][k^1];
for(T=1;T<(1<<n);++T)
for(j=0;j<n;++j)
{
if(!((T>>j)&1))continue;
for(l=0;l<n;++l)
{
if((T>>l)&1)continue;
np=T+(1<<l);
for(k=0;k<2;++k)
{
if(!f[T][j][k])continue;
for(o=0;o<2;++o)
{
nw=f[T][j][k] + delta[j][k^1][l][o^1]*2;
if(!f[np][l][o] || f[np][l][o]>nw)
{
f[np][l][o]=nw;
comeT[np][l][o]=T;
comeI[np][l][o]=j;
comeK[np][l][o]=k;
}
}
}
}
}
int minlen=INF;
string ans;
for(i=0;i<n;++i)
for(o=0;o<2;++o)
if(f[(1<<n)-1][i][o])minlen=min(minlen,f[(1<<n)-1][i][o]);
for(i=0;i<n && !ans.size();++i)
for(o=0;o<2 && !ans.size() ;++o)
if(f[(1<<n)-1][i][o] && f[(1<<n)-1][i][o]==minlen)
{
ans=get((1<<n)-1,i,o);
break;
}
cout<<ans<<endl;
}



  评论这张
 
阅读(301)| 评论(1)
推荐 转载

历史上的今天

评论

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

页脚

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