[BZOJ2806] [Ctsc2012] Cheat(접미사 자동기+단조로운 대기열 최적화 dp)
제목:
하이퍼링크입니다.
문제 풀이:
우리는 먼저 표준 직렬을 하나의 넓은 의미의 접두사 자동기를 하나의 L로 나누고 dp로 타당성을 판단한다. dp?!
우선 우리는 접미사 자동기로 l[i]를 미리 처리하여 i위가 반드시 선택되어 가장 긴 길이와 일치할 수 있음을 나타낸다. 즉, 앞으로 가장 멀리 뻗어 표준 직렬과 일치할 수 있는 길이를 표시한다.
어떻게 dp판으로 가능합니까?f[i]는 앞의 i위를 [익숙]의 최대 길이라고 할 수 있다. 그러면 마지막으로 f[n]와len을 비교해 보면 90%도 안 보이면 된다. f[i]는 어떻게 구하지?전이 방정식 f[i]=max{f[i-1], f[j]+i-j} j∈[i--l[i], i-3L] j∈[i-l[i], i-3L] 이 범위는 우리가 주의해야 할 것이다. i-l[i]는 이 경계를 넘으면 일치하지 않기 때문에 i-j로 길이를 표시할 수 없다.i-L은 [익숙]으로 불리는 한계입니다.
O(n2) O ( n 2 ) ?안 돼요. 빨리 할 수 있는지 최적화해 볼게요. 이 f[i]=f[i-1]는 초치로 할 수 있어요. 물론 i
i+1−l[i]−1<=i+1−l[i+1] i + 1 − l [ i ] − 1 <= i + 1 − l [ i + 1 ]
i−l[i]<=i+1−l[i+1] i − l [ i ] <= i + 1 − l [ i + 1 ]
그래서 i-l[i]는 단조로워서 떨어지지 않습니다. 우리는 단조로운 대기열 유지보수 구간 f[i]-i의 최고치를 사용할 수 있습니다.
우리가 전에 이미 말했듯이 i결점의 이동 구간은 [i-3l[i], i-3L]뿐이다. i가 뒤로 이동할 때마다 유일하게 발생할 수 있는 새로운 이동점은 (i-3L)이다. 그러면 우리는 팀 끝에 이 이동점을 삽입한다. i-3L
새로운 점을 추가한 다음에 헤드를 처리해야 한다는 것을 기억해라, why?i-l[i]가 반드시 i-L보다 작은 것은 아니기 때문에 헤드를 뒤에 놓고 비합법적인 상황을 처리한다.
자신감 넘치고 화려하게 M을 올렸어요...0/1밖에 없는 걸 보고 눈물이 났어요.
코드:
#include
#include
#include
using namespace std;
const int N=2200005;
int np,p,nq,q,last,cnt,ch[N][2],fa[N],step[N],l[N],len,f[N],que[N];
char st[N];
void insert(int c)
{
p=last; np=last=++cnt;
step[np]=step[p]+1;
while (p && !ch[p][c]) ch[p][c]=np,p=fa[p];
if (!p) {fa[np]=1;return;}
q=ch[p][c];
if (step[q]==step[p]+1){fa[np]=q;return;}
nq=++cnt; step[nq]=step[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[nq]=fa[q]; fa[q]=fa[np]=nq;
while (ch[p][c]==q) ch[p][c]=nq,p=fa[p];
}
void init()
{
p=1;int tmp=0;
for (int i=1;i<=len;i++)
{
int c=st[i]-'0';
if (ch[p][c]) p=ch[p][c],tmp++;
else
{
while (p && !ch[p][c]) p=fa[p];
if (!p) p=1,tmp=0;
else tmp=step[p]+1,p=ch[p][c];
}
l[i]=tmp;
}
}
bool check(int L)
{
if (L==0) return 1;
f[0]=0;
int head=1,tail=0;
for (int i=1;i<=len;i++)
{
f[i]=f[i-1];
if (icontinue;
while (head<=tail && f[que[tail]]-que[tail]-L<=f[i-L]-i) tail--;
que[++tail]=i-L;
while (head<=tail && que[head]if (head<=tail) f[i]=max(f[i],f[que[head]]+i-que[head]);
}
return f[len]*10>=len*9;
}
void solve()
{
init();
int l=0,r=len,ans;
while (l<=r)
{
int mid=(l+r)>>1;
if (check(mid)) l=mid+1,ans=mid;
else r=mid-1;
}
printf("%d
",ans);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
cnt=1;
for (int i=1;i<=m;i++)
{
scanf("%s",st+1);
int l=strlen(st+1);last=1;
for (int j=1;j<=l;j++) insert(st[j]-'0');
}
for (int i=1;i<=n;i++)
{
scanf("%s",st+1);
len=strlen(st+1);
solve();
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[프로그래머스/Python] 스택/큐 - 기능개발vs = i: 핵심 적인 부분 반복문 종료 후, 맨 마지막에 현재 vs와 전체 길이의 차를 구해서 나머지들 추가...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.