Typewrite
[Time Limit: 1500 msquad Memory Limit: 262144 kB
]
题意
给出一个字符串 (s)，现在你需要构造出这个字符串，你每次可以花费 (q) 在末尾加上任意一个字符或者花费 (p) 复制任意一段已经构造出来的子串到末尾，问最少需要花费多少。
思路
令 (dp[i]) 表示构造到第 (i) 位最少花费多少。
第一种情况，直接花费 (q) 添加在末尾，(dp[r] = dp[r-1]+q)
第二种情况，花费 (p) 复制一部分到末尾，设 (s[l+1...r]) 是被复制的串，那么此时需要满足 (s[l+1...r] in s[1...l])，则 (dp[r] = dp[l] + p)，此时的问题就是如何维护 (l)。
利用后缀自动机可以表示出所有子串的性质，(pos) 表示满足条件的 (s[l+1...r]) 所在后缀自动机上的节点位置。
每次插入 (s[r]) 时，就是从 (s[l+1...r-1]in s[1...l] implies s[l+1...r] in s[1...l]) 的过程，所以要让 (pos) 节点往 (s[r]) 方向移动。如果能移动的话，直接将 (pos) 移动过去，否则就扩展这个自动机，将 (s[l]) 插入后在尝试能否移动。在这个过程中，不断维护 (pos) 在满足条件范围的节点上。
- 一个问题就是 (pos) 何时不能向 (s[r]) 方向移动，这种情况就是 (pos) 节点不存在 (s[r]) 这条边。
- 令一个问题就是如何维护 (pos) 在符合条件的范围内，我们知道 (pos) 节点包含了同样性质的长度从 (len[fa[pos]]+1) 到 (len[pos]) 内的子串，我们只要保证这里面最短的子串 (len[fa[pos]]+1) 不要太长，需要可以表示出后面那部分的串。在插入 (s[r]) 之前，此时只到 (r-1)，需要保证 (len[fa[pos]]+1 leq (r-1)-(l+1)+1)，插入 (s[r]) 后，此时到了 (r)，需要保证 (len[fa[pos]]+1 leq r-(l+1)+1)
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 2e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
struct Sam {
int node[maxn<<1][27], fa[maxn<<1], step[maxn<<1];
int sz, last;
int newnode() {
mes(node[++sz], 0);
fa[sz] = step[sz] = 0;
return sz;
}
void init() {
sz = 0;
last = newnode();
}
void insert(int k) {
int p = last, np = last = newnode();
step[np] = step[p]+1;
for(; p&&!node[p][k]; p=fa[p])
node[p][k] = np;
if(p == 0) {
fa[np] = 1;
} else {
int q = node[p][k];
if(step[q] == step[p]+1) {
fa[np] = q;
} else {
int nq = newnode();
for(int i=1; i<=26; i++)
node[nq][i] = node[q][i];
fa[nq] = fa[q];
step[nq] = step[p]+1;
fa[np] = fa[q] = nq;
for(; p&&node[p][k]==q; p=fa[p])
node[p][k] = nq;
}
}
}
} sam;
char s[maxn];
ll dp[maxn];
int main() {
while(~scanf("%s", s+1)) {
sam.init();
int len = strlen(s+1);
ll p, q;
scanf("%lld%lld", &q, &p);
ll ans = 0;
int l=0, pos=0;
dp[0] = 0;
for(int r=1; r<=len; r++) {
dp[r] = dp[r-1]+q;
int k = s[r]-'a'+1;
while(!sam.node[pos][k]) {
sam.insert(s[++l]-'a'+1);
while(pos && sam.step[sam.fa[pos]]>r-l-2)
pos = sam.fa[pos];
if(!pos) pos = 1;
}
pos = sam.node[pos][k];
while(pos && sam.step[sam.fa[pos]]>r-l-1)
pos = sam.fa[pos];
if(!pos) pos = 1;
dp[r] = min(dp[r], dp[l]+p);
}
printf("%lld
", dp[len]);
}
return 0;
}