题目描述
给定n个字符串，有以下几种操作：
- 打出一个字符，花费1。
- 删除一个字符，花费1。
- 复制并打出一个之前打出过的字符串，花费k。
求打出所有n个字符串的最小花费。
（注意，打出顺序和字符串输入的顺序不必相同）
题解
显然，操作3需要算字符串的最长公共子序列来处理。
这个问题可以转换为最小生成树问题：
- 目前已经打出的字符串可以被视为最小生成树中已经加入的节点。
- 对于每个字符串，都有两种方式：直接花费length的代价或通过别的点得到。
- 对于第一个字符串，一定会直接花费length的代价得到。
- 那么，就可以设一个虚点0，向所有点建立权值为各自length的边。
由于一定至少有一个字符串会直接话费length打出，那么虚点一定会被加入到最小生成树中。
即最小生成树满足该题的性质。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=107;
int l[N],f[N][N],fa[N],en=0,n,k;
string s[N];
struct Edge{
int u,v,w;
}e[N*N*N];
bool cmp(Edge x,Edge y){
return x.w<y.w;
}
void adde(int u,int v,int w){
e[++en].u=u,e[en].v=v,e[en].w=w;
}
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
int lcs(int x,int y){
for(int i=0;i<=l[x];i++)
for(int j=0;j<l[y];j++)
f[i][j]=0;
for(int i=1;i<=l[x];i++)
for(int j=1;j<=l[y];j++){
if(s[x][i-1]==s[y][j-1]){
f[i][j]=f[i-1][j-1]+1;
}
else{
f[i][j]=max(f[i-1][j],f[i][j-1]);
}
}
return k+l[x]+l[y]-f[l[x]][l[y]]*2;
}
signed main(){
int ans=0;
cin>>n>>k;
for(int i=1;i<=n;i++){
fa[i]=i;
cin>>l[i];
cin>>s[i];
adde(0,i,l[i]);
}
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
adde(i,j,lcs(i,j));
sort(e+1,e+en+1,cmp);
for(int i=1;i<=en;i++){
int u=find(e[i].u),v=find(e[i].v);
if(u==v)continue;
fa[v]=u;
ans+=e[i].w;
}
cout<<ans<<endl;
return 0;
}