hdu3247ac자동기+bfs예처리최단로+상압DP 깊이 이해
붙이는 건 누가 봤으면 안심하고 가져가서 찍거나 공부해. 난 레이펑이라고 해.
코드
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iomanip>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define rep(i,k,n) for(int i=(k);i<=(n);i++)
#define rep0(i,n) for(int i=0;i<(n);i++)
#define red(i,k,n) for(int i=(k);i>=(n);i--)
#define sqr(x) ((x)*(x))
#define clr(x,y) memset((x),(y),sizeof(x))
#define pb push_back
#define mod 1000000007
const int INF=0x3f3f3f3f;
int pos[11];
struct Trie
{
int next[60010][2],fail[60010],end[60010];
int root,L;
int newnode()
{
for(int i=0;i<2;i++)
next[L][i]=-1;
end[L]=0;
return L++;
}
void init()
{
L=0;
root=newnode();
}
int insert(char buf[],int id)
{
int len=strlen(buf);
int now=root;
for(int i=0;i<len;i++)
{
if(next[now][buf[i]-'0']==-1)
next[now][buf[i]-'0']=newnode();
now=next[now][buf[i]-'0'];
}
end[now]=id;
return now;
}
void build()
{
queue<int> Q;
fail[root]=root;
for(int i=0;i<2;i++)
{
if(next[root][i]==-1)
next[root][i]=root;
else
{
fail[next[root][i]]=root;
Q.push(next[root][i]);
}
}
while(!Q.empty())
{
int now=Q.front();
Q.pop();
end[now]|=end[fail[now]];
for(int i=0;i<2;i++)
if(next[now][i]==-1)
next[now][i]=next[fail[now]][i];
else
{
fail[next[now][i]]=next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
int g[11][11];
int dp[1024][11];
int cnt;
int dis[60010];
void bfs(int k)
{
queue<int>q;
memset(dis,-1,sizeof(dis));
dis[pos[k]]=0;
q.push(pos[k]);
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=0;i<2;i++)
{
int tmp=next[now][i];
if(dis[tmp]<0 && end[tmp]>=0)
{
dis[tmp]=dis[now]+1;
q.push(tmp);
}
}
}
for(int i=0;i<cnt;i++)
g[k][i]=dis[pos[i]];
}
int solve(int n)
{
pos[0]=0;
cnt=n+1;
for(int i=0;i<cnt;i++)bfs(i);
for(int i=0;i<(1<<n);i++)
for(int j=0;j<cnt;j++)
dp[i][j]=INF;
dp[0][0]=0;
for(int i=0;i<(1<<n);i++)
for(int j=0;j<cnt;j++)
if(dp[i][j]<INF)
{
for(int k=0;k<cnt;k++)
{
if(g[j][k]<0 || j==k)continue;
dp[i|end[pos[k]]][k]=min(dp[i|end[pos[k]]][k],dp[i][j]+g[j][k]);
}
}
int ans=INF;
for(int j=0;j<cnt;j++)
ans=min(ans,dp[(1<<n)-1][j]);
return ans;
}
};
Trie ac;
char buf[1010];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m),n||m)
{
ac.init();
for(int i=0;i<n;i++)
{
scanf("%s",buf);
pos[i+1]=ac.insert(buf,1<<i);
}
for(int i=0;i<m;i++)
{
scanf("%s",buf);
ac.insert(buf,-1);
}
ac.build();
printf("%d
",ac.solve(n));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.