Hdu 4117 GRE Words （後綴數組+dp）
題目大意：
求出最多能記住的單詞的權值和，要求最大。
記住的規則就是上一個單詞是這個單詞的子串。
思路分析：
首先得聲明這題是數據水了才能用sa做的。
sa的復雜度最多可以達到 Orz（sumlen * sumlen） ...
所以我們sa處理的就是這個串是否是下一個串的子串，如果是就轉移方程。
dp[i] = max (dp[i] , dp[j] + val[i])...
#include
#include
#include
#include
#define maxn 350005
#define inf 0x3f3f3f3f
using namespace std;
int str[maxn];
int sa[maxn],t1[maxn],t2[maxn],c[maxn],n;
int bel[maxn];
int st[maxn],sumlen[maxn],val[maxn];
int dp[maxn];
void suffix(int m)
{
int *x=t1,*y=t2;
for(int i=0;i=0;i--)sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1)
{
int p=0;
for(int i=n-k;i=k)y[p++]=sa[i]-k;
for(int i=0;i=0;i--)sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=1;x[sa[0]]=0;
for(int i=1;i=n)break;
m=p;
}
}
int rank[maxn],height[maxn];
void getheight()
{
int k=0;
for(int i=0;ii)
{
dp[bel[sa[j]]]=max(dp[bel[sa[j]]],val[bel[sa[j]]]+dp[i]);
}
}
mlen=inf;
for(int j=rank[st[i]]-1;j>0;j--)
{
mlen=min(mlen,height[j+1]);
if(mleni)
{
dp[bel[sa[j]]]=max(dp[bel[sa[j]]],val[bel[sa[j]]]+dp[i]);
}
}
}
printf("Case #%d: %d\n",cas++,max(0,*max_element(dp+1,dp+1+N)));
}
return 0;
}
/*
1
6
abbab 800
a 1
ab 2
abb 3
baba 5
abbab 8
*/
