HDU 4511 소명 시리즈 - 여자친구의 시험(AC 오토매틱 + DP)
제목:
중국어 문제.추상적인 문제: 1호점에서 n호점까지의 가장 짧은 경로를 묻고 경로에 하위 문자열을 포함할 수 없습니다.
문제 해결 방법:
사실 어렵지 않다. 만약에'어떤 하위 문자열을 포함할 수 없다'에서 AC자동기를 연상할 수 있다면 이 문제는 기본적으로 해결될 것이다.
dp[i][j]로 하여금 i호점에 도달하고 자동기기의 j노드에 있는 데 걸리는 가장 짧은 거리를 표시하도록 한다.
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define CLR(a,v) memset(a,v,sizeof(a))
typedef pair<double,double> PDD;
PDD p[55];
#define F first
#define S second
double d[55][55];
double sqr(double x)
{
return x * x;
}
double dis(PDD& p1,PDD& p2)
{
return sqrt( sqr(p1.F - p2.F) + sqr(p1.S - p2.S) );
}
namespace Trie
{
const int N = 505;
const int Size = 50;
int top;
struct Node{
Node *next[Size], *f;
bool ended;
}node[N], *root;
inline Node* new_node()
{
node[top].ended = false;
CLR(node[top].next,NULL);
return &node[top++];
}
void init()
{
top = 0;
root = new_node();
}
void insert(char *s)
{
Node *u = root;
for(int i=0;s[i];i++)
{
int id = s[i] - 1;
if(u->next[id] == NULL)
u->next[id] = new_node();
u = u->next[id];
}
u->ended = true;
}
}
namespace ACam
{
using namespace Trie;
void get_fail()
{
queue<Node*> Q;
for(int i=0;i<Size;i++)
{
Node *&ch = root->next[i];
if(!ch)
ch = root;
else
{
ch->f = root;
Q.push(ch);
}
}
while(!Q.empty())
{
Node *cur = Q.front();Q.pop();
for(int i=0;i<Size;i++)
{
Node *&ch = cur->next[i];
if(!ch)
ch = cur->f->next[i];
else
{
ch->f = cur->f->next[i];
ch->ended |= ch->f->ended;
Q.push(ch);
}
}
}
}
double dp[55][N];
double solve(int n)
{
const double inf = 1e12;
fill(&dp[0][0],&dp[54][Size-1],inf);
int state_init = node[0].next[0] - node;
if(node[state_init].ended)
return -1;
dp[0][state_init] = 0;
for(int i=0;i<n-1;i++)
{
for(int j=0;j<top;j++)
{
if(dp[i][j] == inf)
continue;
for(int k=i+1;k<n;k++)
{
int jj = node[j].next[k] - node;
if(node[jj].ended)
continue;
dp[k][jj] = min(dp[k][jj],dp[i][j]+dis(p[i],p[k]));
}
}
}
double ans = inf;
for(int j=0;j<top;j++)
ans = min(ans,dp[n-1][j]);
return ans == inf ? -1 : ans;
}
}
char str[9];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m),n||m)
{
ACam::init();
for(int i=0;i<n;i++)
scanf("%lf%lf",&p[i].F,&p[i].S);
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
d[i][j] = dis(p[i],p[j]);
}
while(m--)
{
int k;
scanf("%d",&k);
for(int i=0;i<k;i++)
{
int id;
scanf("%d",&id);
str[i] = id;
}
str[k] = '\0';
ACam::insert(str);
}
ACam::get_fail();
double ans = ACam::solve(n);
if(ans == -1)
puts("Can not be reached!");
else
printf("%.2f
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.