打字游戏：MST 套 dp 好题。
首先看这个数据范围，\(O(n^4)\) 把每两个字符串之前的编辑距离求一下很显然吧。
然后我们观察一下每一个 node 的性质，发现他要么自己打完，要么从别人那里复制过来。这个就很像一棵树。
建完树之后，我们就得到了一个森林。
那么题目就转化为，求出一个边权之和最小的森林，使得所有点都在森林中。
显然我们可以将森林中的每一个根节点超一个虚拟源点连一条边，这个边的边权是多少？实际上就是空串到他的编辑距离，也就是这个字符串的长度。
那么我们就可以在上面跑 MST 了。
还有一个性质，就是 \(A\) 从 \(B\) 那里复制过来和 \(B\) 从 \(A\) 那里复制过来的代价是一样的，正是因为这个性质，这个东西才是颗树，因为这样才是双向边。不然我们就得跑一个有向图 MST 了。有向图 MST 参考滑雪那题。
时间复杂度 \(O(n^4)\)，瓶颈在于求编辑距离。
代码：
#include <bits/stdc++.h>
#define fi first
#define se second
#define lc (p<<1)
#define rc ((p<<1)|1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
ll n,k,dp[105][105],ans=0,cnt=0;
int f[105];
string s[105];
struct edge{
int u,v;
ll w;
}e[100005];
bool cmp(edge x,edge y)
{
return x.w<y.w;
}
ll cal(string a,string b)
{
for(int i=0;i<=a.length();i++)for(int j=0;j<=b.length();j++)dp[i][j]=0x3f3f3f3f;
for(int i=0;i<=a.length();i++)dp[i][0]=i;
for(int j=0;j<=b.length();j++)dp[0][j]=j;
for(int i=1;i<=a.length();i++)
{
for(int j=1;j<=b.length();j++)
{
if(a[i-1]==b[j-1])dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
dp[i][j]=min(dp[i][j],min(dp[i-1][j]+1,dp[i][j-1]+1));
}
}
return dp[a.length()][b.length()];
}
void init()
{
for(int i=0;i<=n;i++)f[i]=i;
}
int findf(int x)
{
if(f[x]!=x)f[x]=findf(f[x]);
return f[x];
}
void combine(int x,int y)
{
int fx=findf(x),fy=findf(y);
f[fx]=fy;
}
int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
s[0]="";
for(int i=1;i<=n;i++)
{
int x;
cin>>x>>s[i];
}
for(int i=0;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
e[++cnt]={i,j,cal(s[i],s[j])+k*((i!=0)&&(j!=0))};
}
}
sort(e+1,e+cnt+1,cmp);
init();
for(int i=1;i<=cnt;i++)
{
int u=e[i].u,v=e[i].v;
ll w=e[i].w;
int fu=findf(u),fv=findf(v);
if(fu!=fv)
{
combine(fu,fv);
ans+=w;
}
}
cout<<ans;
return 0;
}