题目链接:
https://codeforces.com/contest/1120/problem/C
题意:
从前往后压缩一段字符串
有两种操作:
1. 对于单个字符, 压缩它花费 $a$
2. 对于末尾一段字符串, 如果这段字符串是已经压缩过字符串的子串, 那么可以选择压缩它, 花费为 $b$
数据范围:
- $1\leq |S| \leq 5000$
- $1\leq a \leq 5000$
- $1\leq b \leq 5000$
分析:
这道题目我们需要解决一个问题, 计算某个子串出现的最早位置
转移, 如果这个字串出现的最早位置不是当前位置, 也就是说这个字串在前面还出现了一次, 那么可以执行第二种操作
对于指定状态可以根据子状态转移, 取最小的子状态的最早位置
给出子串下标求出子串出现的最早位置, 首先得到子串在 sam 中的状态, 根据状态得到最早出现的位置
AC 代码:
- #include<bits/stdc++.h>
- #define ll long long
- using namespace std;
- const int maxn=5000+10;
- char S[maxn];
- int n,a,b;
- struct suffixautomation
- {
- int mp[maxn*2][30],fa[maxn*2],ed,ct,len[maxn*2],minpos[maxn*2],deg[maxn*2],pos[maxn][maxn];
- int dp[maxn];
- suffixautomation(){ed=ct=1;}
- inline void ins(int c,int pos)
- {
- int p=ed;ed=++ct;minpos[ed]=pos;len[ed]=pos;// 先初始化 size 和 len
- for(;p&&mp[p][c]==0;p=fa[p]){mp[p][c]=ed;}// 然后顺着 parent 树的路径向上找
- if(p==0){fa[ed]=1;return;}int q=mp[p][c];//case1
- if(len[p]+1==len[q]){fa[ed]=q;return;}//case2
- len[++ct]=len[p]+1;//case 3
- for(int i=1;i<=26;i++){mp[ct][i]=mp[q][i];}
- fa[ct]=fa[q];fa[q]=ct;fa[ed]=ct;
- for(int i=p;mp[i][c]==q;i=fa[i]){mp[i][c]=ct;}
- }
- void solve(){
- for(int i=1;i<=n;i++){
- int now=1;
- for(int j=i;j<=n;j++){
- int v=S[j]-'a'+1;
- now=mp[now][v];
- pos[i][j]=now;
- }
- }
- for(int i=1;i<=ct;i++)deg[fa[i]]++;
- queue<int>que;
- for(int i=1;i<=ct;i++)if(deg[i]==0)que.push(i);
- while(que.size()){
- int x=que.front();
- int y=fa[x];
- que.pop();
- minpos[y]=min(minpos[x],minpos[y]);
- deg[y]--;
- if(deg[y]==0)que.push(y);
- }
- for(int i=1;i<=n;i++){
- dp[i]=dp[i-1]+a;
- for(int j=2;j<=i;j++){
- if(minpos[pos[j][i]]<j){
- dp[i]=min(dp[i],dp[j-1]+b);
- break;
- }
- }
- }
- printf("%d\n",dp[n]);
- }
- }sam;
- int main()
- {
- scanf("%d %d %d",&n,&a,&b);
- scanf("%s",S+1);
- for(int i=0;i<maxn*2;i++)sam.minpos[i]=1e9;
- for(int i=1;i<=n;i++)sam.ins(S[i]-'a'+1,i);
- sam.solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3229484.html