StringWeight
作者：承君阳
关键词：动态规划 贪心
题目简述
本题只出现大写字母。
定义字符串的重量为对于所有出现了的字母，将其最后一次出现的位置-第一次出现的位置加起来得到的数。
定义一个字符串是轻的，当且仅当它是所有同长度的字符串里重量最小的之一。
现在你需要选择个轻的字符串，将它们顺次相接，第个字符串的长度是，问最后得到的字符串的重量最少是多少。
算法
下面的表示字符集大小，本题中为。
考虑在一个子字符串中出现的字母，有四种情况：
1.这是它在总串中唯一一次出现。
2.这是它在总串中第一次出现（不是唯一一次）。
3.这是它在总串中最后一次出现（同上）。
4.这既不是它在总串中第一次出现，也不是最后一次。
在一个子字符串中，显然可以贪心的将2类放在最后，3类放在最前，其他两类放在中间，如果知道每种情况的出现次数就可以得出这个子字符串对答案的贡献。
于是考虑动态规划，对于当前串，我们枚举4种情况的出现次数，考虑前面的串对后面有哪些影响：
1.已经使用过的字母个数
2.已经不能再使用的字母个数
于是我们得到了一个的算法。
接着发现其实我们只需要枚举已经使用过的字母个数的改变量和已经不能再使用的字母个数的改变量，就可以贪心得出4种情况在这个子字符串中的最优出现次数。
于是时间复杂度降为。
时间复杂度为。