Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 720 Accepted Submission(s): 225
题意：
给你一串字符以及单独打印每一个字母的代价，对于一个字母，你可以选择直接打印，也可以选择利用复制粘贴的方法来完成。对于复制粘贴，每次选择长度为i的字符串的代价是i*A，复制的代价是B，粘贴的代价也是B。即复制并粘贴一个长度为x的字符串的代价是x*A+2*B。现在问把这一整个字符串打印出来的代价是多少。
思路：
考虑DP, dp[i]:表示前i个字符打印完成的最小代价，则我们可以得到dp[i]=min(dp[i-1]+val[s[i]] , dp[j]+ (i-j)*A+2*b);那么这样的DP的时间复杂度是O(n^2),对于1e6的数据来说是无法接受的。
我们定义j为最小的一个位置，可以使得1..j的子串包含j+1..i的子串。经过观察，我们可以发现，这个j一定是单调的。也就是说，随着i的变大，j一定只增不减，这个很好理解。如果对于上一个长度来说最小的位置是j，对于当前决策，增加了一个长度，j肯定是要么增加要么不变。所以我们就可以利用这个单调性，用单调队列来优化这个dp.
如何保证在复杂度时间内判断某个串中是否包含另外一个串。也即，字符串s中，一个子串是否包含另外一个子串。如此，还是可能需要用到s的所有的子串，所以说还是用后缀自动机。每次，我们维护j，j的移动取决于前面部分的子串是否包含后面的子串。具体来说，对于当前的j，j+1~i-1在自动机上匹配到的位置x，如果对于新的i，自动机上面如果仍然有后继，那么j不动。如果没有，那么我就要考虑移动j了，移动的过程中，把新的s[j+1]添加到自动机中，继续匹配，如果添加到一定位置，发现x有s[i]这个后继了，那么停止；或者说，当j+1~i-1的长度缩短到x的parent指针所指节点的长度的时候，x则发生跳转，直接跳到其最长的后缀那里去。因为在移动的过程中，需要匹配的串也逐渐变短，短到一定程度就会变成原本串的一个最长后缀。就这样已知移动然后匹配，找到j移动到i或者发现点x有s[i]这个后继。
如此，对于当前i确定了j之后，我们就可以修改单调队列中的值，把所有小于j的决策都去掉，然后再选取目前最优的决策更新。最后把当前的状态结果也当作决策加入单调队列中。一边dp一边维护单调队列和j，同时还不断的把字符添加到SAM中。
参考代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define pli pair<ll,int> #define mkp make_pair const int INF=0x3f3f3f3f; const int maxn=1e5+10; int T; char s[maxn]; int fa[maxn<<1],l[maxn<<1],nxt[maxn<<1][26]; int last,tot; ll val[30],dp[maxn],A,B; pli q[maxn]; void Init() { last=tot=1; l[tot]=fa[tot]=0; memset(nxt[tot],0,sizeof nxt[tot]); } int NewNode() { ++tot; fa[tot]=l[tot]=0; memset(nxt[tot],0,sizeof nxt[tot]); return tot; } void Insert(int ch) { int np=NewNode(),p=last; last=np; l[np]=l[p]+1; while(p&&!nxt[p][ch]) nxt[p][ch]=np,p=fa[p]; if(!p) fa[np]=1; else { int q=nxt[p][ch]; if(l[q]==l[p]+1) fa[np]=q; else { int nq=NewNode(); l[nq]=l[p]+1; memcpy(nxt[nq],nxt[q],sizeof nxt[q]); fa[nq]=fa[q]; fa[np]=fa[q]=nq; while(p&&nxt[p][ch]==q) nxt[p][ch]=nq,p=fa[p]; } } } int main() { scanf("%d",&T); for(int cas=1;cas<=T;++cas) { Init(); scanf("%s",s+1); int n=strlen(s+1); for(int i=0;i<26;++i) scanf("%lld",&val[i]); scanf("%lld%lld",&A,&B); int pos=1;dp[0]=0; int L=0,R=0,nt=0,j=0,len=0,pa; for(int i=1;i<=n;++i) { int ch=s[i]-‘a‘; dp[i]=dp[i-1]+val[ch]; pa=fa[pos]; nt=nxt[pos][ch]; while(!nt&&j+1<i) { if(pos!=1&&--len==l[pa]) pos=pa,pa=fa[pos]; ++j; Insert(s[j]-‘a‘); nt=nxt[pos][ch]; } if(!nt) { pos=1;L=R=0; ++j; Insert(s[j]-‘a‘); } else pos=nt,++len; while(L<R && q[L].second<j) ++L; if(L!=R) dp[i]=min(dp[i],q[L].first+1ll*i*A+2ll*B); q[R++]=mkp(dp[i]-i*A,i); while(L<R-1&&q[R-1].first<=q[R-2].first) --R,q[R-1]=q[R]; } printf("Case #%d: %lld\n",cas,dp[n]); } return 0; }
HDU5470 Typewriter （SAM+单调队列优化DP）
原文：https://www.cnblogs.com/songorz/p/11478705.html
