\u60f3\u4e86\u534a\u5929\u3002\u3002\u53d1\u73b0\u5c45\u7136\u662f\u4e00\u4e2a\u6700\u77ed\u54c8\u5bc6\u987f\u8def\u7684\u6a21\u578b\uff08\u6ce8\u610f\u4e0d\u662f\u73af\u3002\u3002\uff09
\u9996\u5148\u628a\u88ab\u5305\u542b\u7684\u6254\u6389\u3002\u3002\u90a3\u4e48\u5efa\u7acbN\u4e2a\u9876\u70b9\u4ee3\u8868\u5b57\u7b26\u4e32\u3002\u3002
\u4e24\u70b9\u7684\u8ddd\u79bb\u5c31\u662f\u8fd9\u4e24\u4e2a\u5b57\u7b26\u4e32\u63a5\u8d77\u6765\u589e\u52a0\u7684\u5b57\u7b26\u6570*2\u3002\u3002
\u56fe\u662f\u5b8c\u5168\u7684\u3002\u3002\u8fb9\u662f\u6709\u5411\u7684\u3002\u3002
\u90a3\u4e48\u7528\u96c6\u5408DP\u5c31\u53ef\u4ee5\u641e\u5b9a\u4e86\u3002\u3002\u5148\u8981\u679a\u4e3e\u5f00\u59cb\u7684\u9876\u70b9\u3002\u3002
\u590d\u6742\u5ea6\u5c31\u662f\uff08N^3*2^N\uff09\u3002\u3002\u4e5f\u80fd\u8fc7\u3002\u3002
\u3002\u3002\u6b63\u5728\u5199\u3002\u3002
\u5199\u4e86\u534a\u5929\u3002\u3002\u5f04\u4e86\u4e2a\u534a\u6210\u54c1\u3002\u3002\u8def\u5f84\u5b9e\u5728\u4e0d\u60f3\u5199\u4e86\u3002\u3002\u53ea\u80fd\u7b97\u4e2a\u7b54\u6848
\u6ce8\u610f\u4e00\u4e0b\u3002\u3002\u8fde\u63a5\u7684\u8bdd\u6709\uff14\u79cd\u65b9\u5f0f(\uff34\u8868\u793a\u6b63\u7684\u653e\u3002\u3002\uff32\u8868\u793a\u53cd\u7740\u653e)
T<- T R -> R
R<- R T -> T
T<- R T -> R
R<- T R -> T
\u3002\u3002\u3002\uff22\uff34\u3002\u3002\u3002
\u8fd9\u4e48\u641e\u7684\u8bdd\u518d\u6784\u9020\u65b9\u6848\u5c82\u4e0d\u662f\u8981\u6b7b\u4eba\u963f\u3002\u3002
Code\u3002\u3002
#include<string>
#include<iostream>
#include<queue>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=14,inf=~0U>>1;
int N=0,ans=~0U>>1;
string B[maxn];
int dist[maxn][maxn];
string Reverse(string tmp)
{
for(int s=0,t=tmp.length()-1;s<t;s++,t–) swap(tmp[s],tmp[t]);
return tmp;
}
int maxcommon(const string&x,const string&y)
{
int ans=0;
for(int i=1;i<=min(x.length(),y.length());i++)
if(x.substr(x.length()-i,i)==y.substr(0,i))
ans=i;
return ans;
}
void init()
{
int cnt;cin>>cnt;
string A[maxn];
for(int i=0;i<cnt;i++)
cin>>A[i];
for(int i=0;i<cnt;i++)
{
bool find=false;
for(int j=0;j<cnt;j++) if(j!=i)
if(A[j].find(A[i])!=string::npos)
{find=true;break;}
if(!find)
B[N++]=A[i];
}
for(int i=0;i<N;i++)
for(int j=0;j<N;j++) if(i!=j)
{
int a=B[j].length()*2-maxcommon(B[j],B[i])*2;
int b=B[j].length()*2-maxcommon(Reverse(B[j]),B[i])*2;
int c=B[j].length()*2-maxcommon(B[j],Reverse(B[i]))*2;
int d=B[j].length()*2-maxcommon(Reverse(B[j]),Reverse(B[i])))*2;
dist[i][j]=min(min(min(a,b),c),d);
}
}
int DP[1<<maxn][maxn];
struct node
{
int state,pos;
node(int s,int p):state(s),pos(p){}
};
void start(int i)
{
string tmp=Reverse(B[i]);
REP(j,1<<N) REP(k,N) DP[j][k]=inf;
DP[1<<i][i]=B[i].length()*2-maxcommon(B[i],tmp);
queue<node> Q;
Q.push(node(1<<i,i));
while(Q.size())
{
node cur=Q.front();Q.pop();
int s=cur.state,p=cur.pos;
for(int j=0;j<N;j++) if(s^(1<<j))
{
int ns=s^(1<<j),get=DP[s][p]+dist[p][j];
if(DP[ns][j]>get)
DP[ns][j]=get,Q.push(node(ns,j));
}
}
REP(j,N) if(DP[(1<<N)-1][j]<ans)
ans=DP[(1<<N)-1][j];
}
void solve()
{
for(int i=0;i<N;i++)
start(i);
cout<<ans<<endl;
}
int main()
{
init();
solve();
} <\/p>\n","protected":false},"excerpt":{"rendered":"
\u60f3\u4e86\u534a\u5929\u3002\u3002\u53d1\u73b0\u5c45\u7136\u662f\u4e00\u4e2a\u6700\u77ed\u54c8\u5bc6\u987f\u8def\u7684\u6a21\u578b\uff08\u6ce8\u610f\u4e0d\u662f\u73af\u3002\u3002\uff09\u9996\u5148\u628a\u88ab\u5305\u542b\u7684\u6254\u6389\u3002\u3002\u90a3\u4e48\u5efa\u7acbN\u4e2a\u9876\u70b9\u4ee3\u8868\u5b57\u7b26\u4e32\u3002\u3002\u4e24\u70b9\u7684\u8ddd\u79bb\u5c31\u662f\u8fd9\u4e24\u4e2a\u5b57\u7b26\u4e32\u63a5\u8d77\u6765\u589e\u52a0\u7684\u5b57\u7b26\u6570*2\u3002\u3002\u56fe\u662f\u5b8c\u5168\u7684\u3002\u3002\u8fb9\u662f\u6709\u5411\u7684\u3002\u3002\u90a3\u4e48\u7528\u96c6\u5408DP\u5c31\u53ef\u4ee5\u641e\u5b9a\u4e86\u3002\u3002\u5148\u8981\u679a\u4e3e\u5f00\u59cb\u7684\u9876\u70b9\u3002\u3002\u590d\u6742\u5ea6\u5c31\u662f\uff08N^3*2^N\uff09\u3002\u3002\u4e5f\u80fd\u8fc7\u3002\u3002\u3002\u3002\u6b63\u5728\u5199\u3002\u3002\u5199\u4e86\u534a\u5929\u3002\u3002\u5f04\u4e86\u4e2a\u534a\u6210\u54c1\u3002\u3002\u8def\u5f84\u5b9e\u5728\u4e0d\u60f3\u5199\u4e86\u3002\u3002\u53ea\u80fd\u7b97\u4e2a\u7b54\u6848\u6ce8\u610f\u4e00\u4e0b\u3002\u3002\u8fde\u63a5\u7684\u8bdd\u6709\uff14\u79cd\u65b9\u5f0f(\uff34\u8868\u793a\u6b63\u7684\u653e\u3002\u3002\uff32\u8868\u793a\u53cd\u7740\u653e)T<- T R -> RR<- R T -> TT<- R T -> RR<- T R -> T\u3002\u3002\u3002\uff22\uff34\u3002\u3002\u3002\u8fd9\u4e48\u641e\u7684\u8bdd\u518d\u6784\u9020\u65b9\u6848\u5c82\u4e0d\u662f\u8981\u6b7b\u4eba\u963f\u3002\u3002Code\u3002\u3002#include<string>#include<iostream>#include<queue>#define REP(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=14,inf=~0U>>1;int N=0,ans=~0U>>1;string B[maxn];int dist[maxn][maxn];string Reverse(string tmp){ for(int s=0,t=tmp.length()-1;s<t;s++,t–) swap(tmp[s],tmp[t]); return tmp;}int maxcommon(const string&x,const string&y){ int ans=0; for(int i=1;i<=min(x.length(),y.length());i++) if(x.substr(x.length()-i,i)==y.substr(0,i)) ans=i; return ans;}void init(){ int cnt;cin>>cnt; string A[maxn]; for(int i=0;i<cnt;i++) cin>>A[i]; for(int i=0;i<cnt;i++) […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/20"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=20"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/20\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=20"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=20"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=20"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}