Greedy 1472F 从左到右考虑每一列， 确定了前 $i-1$ 列，那么现在的第 $i$ 列哪些被覆盖就确定了。 可以求出第 $i$ 列覆盖的方案：如果没有空格/只有一个空格，则只能放横的；否则两个都是空格，一种是放两个横的，一种是放一个竖的，可以发现放两个横的和放两个竖的等价，不如变成放竖的，其它的之后再决策。 所以就变成，只要这一列没满，…

设一个由小括号和中括号组成的串 $S$ 的权值为 $\sum_{S_i\in{\texttt{'(',')'}}} A_i+\sum_{S_i\in{\texttt{'[',']'}}} B_i$。 求所有的合法的由小括号和中括号组成的长度为 $N$ 的串中最大的权值是多少。 $2\leq N\leq 10^5,2\mid N,1\leq A_i,…