bzoj2580 [Usaco 2012 Jan] Video Game AC 자동기 + dp
#include
#include
#include
#include
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define inf 0xc3c3c3c3
using namespace std;
const int N=1e5+5;
int ch[N][5];
char s[N];
int tag[N],cnt=1;
int fail[N],q[N];
int f[1005][500];
int num[N];
int n,K;
inline void add(int x,int k)
{
memset(ch[cnt],0,sizeof(ch[cnt]));
num[cnt]=0;
ch[x][k]=cnt++;
}
inline void ins()
{
int n=strlen(s);
int x=0;
fo(i,0,n-1)
{
int c=s[i]-'A';
if (!ch[x][c])add(x,c);
x=ch[x][c];
}
num[x]++;
}
inline void acmach()
{
int w=1;
int x;
q[0]=0;
fo(i,0,w-1)
{
x=q[i];
num[x]+=num[fail[x]];
fo(j,0,2)
if (ch[x][j])
{
q[w++]=ch[x][j];
if (!x)fail[ch[x][j]]=0;
else fail[ch[x][j]]=ch[fail[x]][j];
}
else ch[x][j]=ch[fail[x]][j];
}
}
inline void dp()
{
memset(f,0xc3,sizeof(f));
f[0][0]=0;
fo(i,0,K-1)
fo(j,0,cnt-1)
if (f[i][j]!=inf)
fo(k,0,2)
{
int x=ch[j][k];
f[i+1][x]=max(f[i+1][x],f[i][j]+num[x]);
}//f[i][ch[j][k]]=max(f[i][ch[j][k]],f[i-1][j]+num[ch[j][k]]);
}
int main()
{
scanf("%d%d",&n,&K);
num[0]=0;
memset(ch[0],0,sizeof(ch[0]));
cnt=1;
fo(i,1,n)
{
scanf("%s",s);
ins();
}
acmach();
dp();
int ans=0;
fo(i,0,cnt-1)ans=max(ans,f[K][i]);
printf("%d
",ans);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
bzoj1010 장난감 포장 [결정 단조성 최적화 dp]하나의 모범 문제라고 할 수 있다.우리는 먼저 소박한 dp방정식을 얻을 수 있다. f[i]=min(f[j]+w(j,i)),j∈[0,i). w(j,i)는 j+1~i를 포장하여 운송하는 비용의 시간 복잡도는 O(n2)라...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.