CVBB ACM Team

题意:给一个序列 $a$，找一个递增序列$b$ 使得$a_{b_1}-a_{b_2}+a_{b_3}-a_{b_4}+\cdots$最大，有 $q$ 次交换，每次交换 $a_l, a_r$ 并询问交换后的最大值。

题解:观察所求的式子与 $a$ 的关系，显然若是 $a_i > a_{i + 1}$ 直接将这两个数加入答案一定是增加的，若 $a_i < a_{i + 1}$ 则只加一个 $a_{i + 1}$ 则会更优，考虑最后一位的特殊性令 $a_{n + 1} = 0$ 即可，只需维护差分数组即可，答案即为正差分的和，考虑交换操作，修改差分数组即可。

题意:给定一个 $0, 1$ 串，$(i,j)$ 对答案有贡献当且仅当 $a_i = a_j = 1$ 并且 $\exists k,i < k < j,a_k = 1$ ，每秒可以将一个 $1$ 向左或者右侧非 $1$ 处移动，问 $0 \sim \frac{n(n - 1)}{2}$ 秒答案的最大值，$n \le 80$。

题解:$f[i][j][k]$ 表示第 $i$ 位为 $1$ ，前 $i$ 位有 $j$ 个 $1$ ，操作了 $k$ 秒的最大值，转移即可。WA4后不知道哪里错了，突然发现 $zyf$ 也WA4了，错的一样，老犯病了。