HDU 2296 링(AC 로봇 + DP 로깅 시나리오)
제목:
m에 값을 가진 열을 주고 길이가 n인 열을 구성하여 전체 열의 값을 최대화하고 사전 순서를 최소화하는 방안을 출력합니다.
문제 해결 방법:
dp[i][j]로 하여금 길이를 i로 표시하고 자동기 노드 j가 구성할 수 있는 최대 권한을 나타낸다.
상태와 작법은 위의 제목과 유사하게 폭력 기록 방안을 작성한다.
#include <queue>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define CLR(a,v) memset(a,v,sizeof(a))
namespace Trie
{
const int N = 1111;
const int Size = 26;
int top;
struct Node{
Node *next[Size], *f;
int ended_val;
}node[N], *root;
inline Node* new_node()
{
node[top].ended_val = 0;
CLR(node[top].next,false);
return &node[top++];
}
void init()
{
top = 0;
root = new_node();
}
void insert(char *s,int val)
{
Node *u = root;
for(int i=0;s[i];i++)
{
int id = s[i] - 'a';
if(u->next[id] == NULL)
u->next[id] = new_node();
u = u->next[id];
}
u->ended_val = val;
}
}
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_val += ch->f->ended_val;
Q.push(ch);
}
}
}
}
int dp[52][1111];
char sol[52][1111][55],tmp[55],add[2];
bool less(char *a,char *b)
{
int la = strlen(a);
int lb = strlen(b);
return la < lb || la == lb && strcmp(a,b) < 0;
}
void solve(int n)
{
memset(dp,-1,sizeof(dp));
dp[0][0] = 0;
sol[0][0][0] = add[1] = '\0';
for(int i=0;i<n;i++)
{
for(int j=0;j<top;j++)
{
if(dp[i][j] == -1)
continue;
for(int k=0;k<Size;k++)
{
add[0] = 'a' + k;
strcpy(tmp,sol[i][j]);
strcat(tmp,add);
int jj = node[j].next[k] - node;
int val = dp[i][j] + node[jj].ended_val;
if(dp[i+1][jj] < val || dp[i+1][jj] == val && less(tmp,sol[i+1][jj]))
{
dp[i+1][jj] = val;
strcpy(sol[i+1][jj],tmp);
}
}
}
}
int mmax = 0;
char ans[52];
ans[0] = '\0';
for(int i=1;i<=n;i++)
for(int j=0;j<top;j++)
{
if(dp[i][j] > mmax || dp[i][j] == mmax && less(sol[i][j],ans))
{
mmax = dp[i][j];
strcpy(ans,sol[i][j]);
}
}
puts(ans);
}
}
const int N = 52;
char str[102][13];
int main()
{
//freopen("out.ads","w",stdout);
int T,n,m;
scanf("%d",&T);
while(T--)
{
ACam::init();
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
scanf("%s",str[i]);
for(int i=0;i<m;i++)
{
int val;
scanf("%d",&val);
ACam::insert(str[i],val);
}
ACam::get_fail();
ACam::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에 따라 라이센스가 부여됩니다.