AcWing 2868. 子串分值 原题链接：https://www.acwing.com/problem/content/2871/ 具体分析过程如下图： 直接遍历的话太麻烦，且时间复杂度太高，所以另寻他路 字符串中只有小写字母26个，所以可以从此着手， 考虑每个字母对答案的贡献度 那么枚举仅包含一个i的区间的左右端点 代码如下： #include <iostream>

Description 传送门 题解 不想写了所以下面没有代码 看题解发现我第一步就自闭了…感觉我在这种题从来都不会想DP的事情… 设一个 f [ i ] [ j ] f[i][j] f[i][j]表示 [ i , j ] [i,j] [i,j]的答案是什么 如果我们找到了这个区间的最大值位置 p p p，那么显然要不你就是让人们全部走到最大值的左边，要不就是走到最大值的右边 那么转