分享我自己一个有趣的思路

回复帖子

@徐恺 2021-09-15 13:56 回复

首先,我并没有用这个思路做出这道题,但我认为这个思路挺有意思的。

将字符串记为s,我们从s[i]向s[i + 1]连一条有向边,表示打乱后的字母表中,字母s[i]排在s[i + 1]的前面。这样的话,如果最后建成的图是一张有向无环图的话那么这样的字母表就是合法的。

由于可能存在重边,便将边(i, j)(解释,这里的点i和j都是字母)的边权w[i, j]定义为边(i, j)的条数。

这时我们就得到了一张有向边带权的图,我们需要通过删边的操作将图变为无环图。将删去边(i, j)这一操作对应在此题中,意义是在每一组字母i和字母j相邻的地方进行一次划分,也就是划分成前后两遍牛文。删去边(i, j),ans累加上w[i]。最后的答案就是ans + 1。

于是我们将此题转化成了一个图上问题:给定一个有向图(可能存在环和自环),每条边有边权。现删去若干条边使得图中不存在环,求删去边的权值和的最小值。

然而这个问题我还是不会写,只是理论上能够这样进行转换。若有问题欢迎大佬指点。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。