https://ac.nowcoder.com/acm/contest/64593

• A题签到
• B题值得说得是对非降序的理解：非降序表示数组中的前一个数要<=下一个数
• C题也算dp，因为需要注意遍历顺序，计算的是所有子串的的权重，我们知道枚举所有子串需要\(O(n^2)\)的复杂度，按照本题数据范围显然不能\(O(n^3)\)，我们只能在枚举过程中去维护计算每个字串的权重。
  本题的特点是一个str的起点一旦确定，它变换的最终形态也就确定。所以我们考虑枚举起点，再枚举终点，对于每个起点终点确定的子串我们考虑假设起点是0的话我们需要变换c0次，起点是1的话我们需要操作c1次，两者取最小值就是当前子串的权重。

那怎么快速求出每个子串需要变换次数呢？

以下操作都是在起点确定的情况下进行，一旦起点迭代，我们需要重新维护c0，c1。

• 这就需要dp的思想了，我们需要从上一个状态转移过来，上一个状态也就是起点相同，长度比当前短1的子串，这样来看我们只需要处理新出现这个字符即可，根据这个字符是0还是1以及与起点的距离来维护c0，c1。我们可以看到在起点固定的一轮循环中，c0，c1是不断变化的，所以我们要及时累加答案。