构造最优解

2196D

给定一个有两种类型的括号，长度为偶数的字符串。最少需要修改多少字符，才能让所有圆括号组成的子序列构成 RBS，且所有方括号组成的子序列构成 RBS？

假设已经确定最终序列的匹配方式，那么一对位置的操作次数只可能是 0、1 或 2。

用栈进行同种括号匹配，代价为 0。

只有当一对括号两边都朝外时才会产生代价 2，考虑充要条件。考虑先将所有左括号两两匹配，然后将所有右括号两两匹配，这样操作的代价都为 1。此时若所有括号都匹配完成，那说明构造出了最优解。否则，一定会剩下左右括号各一个。如果初始所有左括号都在右括号之后，那么这种情况无可避免，最后配对时会产生代价 2。否则，一定可以通过调整配对方式使得剩下的左括号在右括号之前，所以最后将它俩合并有只会花代价 1，达成最优解。

因此，如果序列满足前缀为右括号，后缀为左括号，且两边数量都为奇数时，会产生一个代价 2 的配对。否则，不会产生。

1526D

给定一个仅包含 4 种字符的字符串 $A$。构造一个字符串 $B$，使得 $B$ 是 $A$ 的一个排列，且最大化通过交换相邻字符将 $B$ 变为 $A$ 所需的最少交换次数。

将相同字符放在一起一定不劣。

1411D

给定 $X,Y$ 和一个由字符 $0$、$1$ 和 $?$ 组成的字符串 $S$。每出现一次子序列 $01$，会产生 $X$ 的代价；每出现一次子序列 $10$，会产生 $Y$ 的代价。你需要将所有的 $?$ 替换为 $0$ 或 $1$，使得总代价尽可能少。