做网站开发建筑设计网站 知乎

题目大意

有一个键盘，上面有$n+1$个按键，按下按键$1\le i\le n$会打印出字符串$S_i$，按下按键$n+1$会删掉结尾的$K$个字符，如果不足$K$个字符则全部删完，问打印出$S$最少要按多少次。

有$T$组数据。

$1\le T\le 100,10\le n\le 5\times 10^3,1\le \sum K\le 2\times 10^3$

$1\le \sum (\sum |S_i|)\le 10^6,1\le \sum |S|\le 5\times 10^3$

时间限制$2000ms$，空间限制$512MB$。

题解

考虑$DP$，设$f_i$表示打出前$i$个字符需要的最小操作次数。那我们要求的就是打出$S$的第$i$个字符到第$j$个字符需要的最小操作次数。

先考虑如何得到$S$中$[i,j]$这一段。我们选择一个前$j-i+1$个字符与$S$的$[i,j]$中的字符相同的$S_p$，然后将$S_p$打出并删到只剩下$S$的$[i,j]$这部分即可。我们可以建一棵字典树，每次加入一个$S_i$时更新从根节点到达路径上每个点的最小操作次数。为了求这里的最小操作次数，我们还需要求出删除若干个字符所需要的最小操作次数，这个可以用一个类似“同余”的最短路来求出，用$\text{dijkstra}$可以$O(K^2)$解决（连边是$O(k^2)$的，求最短路是$O(K\log K)$的）。

得到了带到每个位置的最小操作次数之后，枚举每个$i$，然后在字典树上按$S$从$i$往后枚举，设枚举到$j$，则用$f_i$来更新$f_j$。$DP$的时间复杂度为$O(|S{|}^2)$。

总时间复杂度为$O(\sum (\sum |S_i|+|S{|}^2+K^2))$。

可以参考代码帮助理解。

code

#include<bits/stdc++.h>
using namespace std;
const int N=5000,M=1000000,K=2000;
int T,n,k,s1,now,bg[N+5],len[N+5],z[K+5],vs[K+5],cm[K+5];
int tot;
char s[N+5],t[M+5],ss[M+5];
long long dis[K+5],to[M+5],f[N+5];
struct node{int x;long long dis;bool operator<(const node ax)const{return dis>ax.dis;}
};
vector<pair<int,int>>g[K+5];
priority_queue<node>q;
struct trie{int a[26];
}w[M+5];
void pt(){int len=strlen(ss+1);for(int i=1;i<=len;i++){t[++now]=ss[i];}
}
void init(){for(int i=0;i<k;i++){z[i]=1e9;vs[i]=cm[i]=0;g[i].clear();}for(int i=1;i<=n;i++){len[i]=bg[i+1]-bg[i];z[len[i]%k]=min(z[len[i]%k],len[i]);vs[len[i]%k]=1;}for(int i=1;i<=n;i++){if(z[len[i]%k]!=len[i]) continue;if(!vs[len[i]%k]) continue;vs[len[i]%k]=0;for(int j=0;j<k;j++){g[(j+len[i])%k].push_back({j,1+(j+len[i])/k});}}for(int i=0;i<k;i++) dis[i]=1e16;dis[0]=dis[k]=0;q.push((node){0,0});while(!q.empty()){int u=q.top().x;q.pop();if(cm[u]) continue;cm[u]=1;for(auto p:g[u]){int v=p.first,w=p.second;if(dis[u]+w<dis[v]){dis[v]=dis[u]+w;q.push((node){v,dis[v]});}}}
}
void pt(int tw){int q,vq=1;for(int i=1;i<=len[tw];i++){q=t[bg[tw]+i-1]-'a';if(!w[vq].a[q]){w[vq].a[q]=++tot;to[tot]=1e16;}vq=w[vq].a[q];to[vq]=min(to[vq],1ll+(len[tw]-i)/k+dis[(len[tw]-i)%k]);}
}
void solve(int tw){int q,vq=1;for(int i=tw+1;i<=s1;i++){q=s[i]-'a';if(!w[vq].a[q]) return;vq=w[vq].a[q];f[i]=min(f[i],f[tw]+to[vq]);}
}
int main()
{
//	freopen("keyboard.in","r",stdin);
//	freopen("keyboard.out","w",stdout);scanf("%d",&T);while(T--){scanf("%d%d",&n,&k);now=0;for(int i=1;i<=n;i++){scanf("%s",ss+1);bg[i]=now+1;pt();}bg[n+1]=now+1;scanf("%s",s+1);s1=strlen(s+1);init();tot=1;for(int i=1;i<=n;i++) pt(i);for(int i=0;i<=s1;i++) f[i]=1e16;f[0]=0;for(int i=0;i<s1;i++) solve(i);if(f[s1]>=1e16) printf("-1\n");else printf("%lld\n",f[s1]);for(int i=1;i<=tot;i++){for(int j=0;j<26;j++) w[i].a[j]=0;}}return 0;
}