传送门：https://atcoder.jp/contests/arc066/tasks
前言：又被神奇的dp虐了。
C.水
D.神奇的计数dp
题目大意: 问有多少对
经典结论:
所以v不超过n,那么u就不会超过n.所以直接枚举v. 即从最高位开始枚举 a , b.的每一位.
可能有三种情况:
首先:(0,1)会和其他两种情况构成不同的u.
(0,0)和(1,1)虽然u是一样的，但是v一定不一样.
。假设原来的数大小为:
三种情况对应三种等式:
1.
2.
3.
得到等式：
边界条件:
记忆化搜索即可。
E.又是挺妙的dp
题目大意:给你一个含有 '+' '-' 的算式，问你如何加括号使得算式结果最大.求最大的结果.(n <= 1e5)
题目思路:
经典结论:括号嵌套层数超过三层，一定有一种方法使得其等效成嵌套层数为2层的或者1层的。换句话说：嵌套层数 <= 2 时足以表示所有情况.而且左括号只会打在负号的后面。
那么不难表示状态:
对于每一位.不难想到有以下几种决策:
1.不加任何括号,将 (j % 2 ? -1 : 1) * a[i] 加入答案
2.加一个左括号在数之前。前提是当前这一位是负号 将 (j % 2 ? -1 : 1) * a[i] 加入答案
3.加x个右括号在数之后 将 (j + x % 2 ? -1 : 1) * a[i] 加入答案
注意：3是一个很坑的点，有些情况确实需要在某个数之后加多个右括号。但是要加左括号，只需要加1个。加两个左括号无意义.
AC代码:https://atcoder.jp/contests/arc066/submissions/17130576
