原文链接https://www.cnblogs.com/zhouzhendong/p/HDU5470.html
题目传送门 - HDU5470
题意
你需要写一个只包含小写字母的字符串 $s$ 。
你有两种操作：
1. 在当前写好的字符串的末尾加上一个字符 $c$ ，代价是 $cost_c$ ，所有的 $cost_c$ 都会给出。
2. 在已经写好的字符串中，选择一段子串 $a$ ，复制，并粘贴一次。代价是 $A imes |a|+B imes 2$ 。其中 $A$ 和 $B$ 会给出。
问你写完字符串的最少花费是多少。
多组数据，$Tleq 100,|s|leq 10^5,sum |s| leq 1.2 imes 10^6, 1leq A,B,cost_cleq 10^9$
题解
首先，我们看到这种涉及子串和末尾加上字符的题目，自然想到 SAM ，所以先建一个 SAM 再说。
我们令 $dp_i$ 表示写完前 $i$ 个字符的最小花费。则每一个 $dp_i$ 有两种转移方式，一种是直接加字符，一种是复制粘贴。直接加字符的转移很容易，但是复制粘贴的转移方案很多。
我们考虑一个 $dp_i$ 通过复制粘贴对后面的 $dp$ 值的贡献。有一个很显然的结论：它所能贡献的区域一定是一个连续段。考虑从第 $i+1$ 个位置开始取串，在由第 $i$ 个前缀构成的 SAM 上面走，得到能匹配的最长串，则比它短的显然都能匹配。我们再分析一下贡献的性质：贡献为 串长 × A + 2 × B 。是一个等差数列，我们显然可以线段树搞一下。
现在我们回到之前，考虑如何求那个区间。区间下界显然是 $0$ ，那么问题在求区间上界，以第 $i$ 个字符为左端点，开始与第 $i-1$ 个前缀的子串匹配，我们记最远匹配点为 $R_i$ 。首先我们预处理一下每一个节点的 $right$ 集合中最小的位置，设为 $Time_i$，这样只要走到的节点 $x$ 满足 $Time_x<y$ ，我们就可以在第 $y-1$ 个前缀找到相应的匹配串。再有一个显然的结论，$R_i$ 是单调不降的。因为只需要截掉当前匹配串的第一个字母，就可以转移到下一个位置的匹配，而且是一定匹配的。所以我们可以考虑双指针单调扫一遍，把所有的 $R_i$ 都算出来。
既然 $R_i$ 是单调的，而且我们需要区间更新 min 的等差数列数列的公差都是 $A$ ，所以我们可以考虑单调队列优化一下，这样就不需要写线段树了。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100005;
int T,n,Case=0;
int R[N],c[26],A,B;
int Time[N<<1],tax[N],id[N<<1];
char s[N];
LL dp[N],v[N],q[N],head,tail;
struct SAM{
int Next[26],fa,Max;
}t[N<<1];
int size;
void init(){
memset(t,0,sizeof t);
memset(Time,63,sizeof Time);
size=1,t[0].Max=-1;
for (int i=0;i<26;i++)
t[0].Next[i]=1;
}
int extend(int p,int c){
if (t[p].Next[c]&&t[p].Max+1==t[t[p].Next[c]].Max)
return t[p].Next[c];
int np=++size,q,nq;
t[np].Max=t[p].Max+1;
for (;!t[p].Next[c];p=t[p].fa)
t[p].Next[c]=np;
q=t[p].Next[c];
if (t[p].Max+1==t[q].Max)
t[np].fa=q;
else {
nq=++size;
t[nq]=t[q],t[nq].Max=t[p].Max+1;
t[np].fa=t[q].fa=nq;
for (;t[p].Next[c]==q;p=t[p].fa)
t[p].Next[c]=nq;
}
return np;
}
void Get_Time(){
memset(tax,0,sizeof tax);
for (int i=1;i<=size;i++)
tax[t[i].Max]++;
for (int i=1;i<=n;i++)
tax[i]+=tax[i-1];
for (int i=1;i<=size;i++)
id[tax[t[i].Max]--]=i;
for (int i=size;i>1;i--)
Time[t[id[i]].fa]=min(Time[t[id[i]].fa],Time[id[i]]);
}
int main(){
scanf("%d",&T);
while (T--){
scanf("%s",s+1);
n=strlen(s+1);
init();
for (int i=1,p=1;i<=n;i++)
Time[p=extend(p,s[i]-'a')]=i;
Get_Time();
for (int i=0;i<26;i++)
scanf("%d",&c[i]);
scanf("%d%d",&A,&B);
for (int i=1,j=0,p=1,len=0;i<=n;i++){
while (1){
int Next=t[p].Next[s[j+1]-'a'];
while (!(Next&&Time[Next]<i)&&j-t[t[p].fa].Max<i)
p=t[p].fa,len=t[p].Max,Next=t[p].Next[s[j+1]-'a'];
if (Next&&Time[Next]<i)
j++,p=Next;
else
break;
}
R[i]=j;
}
head=1,tail=0;
memset(q,0,sizeof q);
dp[0]=0;
for (int i=1;i<=n;i++){
dp[i]=dp[i-1]+c[s[i]-'a'];
while (head<=tail&&R[q[head]+1]<i)
head++;
if (head<=tail)
dp[i]=min(dp[i],v[q[head]]+1LL*A*i+B*2);
v[i]=dp[i]-1LL*A*i;
if (R[i+1]>i){
while (head<=tail&&v[i]<=v[q[tail]])
tail--;
q[++tail]=i;
}
}
printf("Case #%d: %lld
",++Case,dp[n]);
}
return 0;
}