傳送門：https://atcoder.jp/contests/arc066/tasks
前言：又被神奇的dp虐了。?
C.水
D.神奇的計(jì)數(shù)dp
題目大意: 問(wèn)有多少對(duì)
經(jīng)典結(jié)論:
所以v不超過(guò)n,那么u就不會(huì)超過(guò)n.所以直接枚舉v. 即從最高位開(kāi)始枚舉 a , b.的每一位.
可能有三種情況:
首先:(0,1)會(huì)和其他兩種情況構(gòu)成不同的u.
(0,0)和(1,1)雖然u是一樣的逻住，但是v一定不一樣.
盐茎。假設(shè)原來(lái)的數(shù)大小為:
三種情況對(duì)應(yīng)三種等式:
?1.
2.
3.
得到等式：
邊界條件:
記憶化搜索即可。
E.又是挺妙的dp
題目大意:給你一個(gè)含有 '+' '-' 的算式蜒灰，問(wèn)你如何加括號(hào)使得算式結(jié)果最大.求最大的結(jié)果.(n <= 1e5)
題目思路:
經(jīng)典結(jié)論:括號(hào)嵌套層數(shù)超過(guò)三層淌铐，一定有一種方法使得其等效成嵌套層數(shù)為2層的或者1層的。換句話說(shuō)：嵌套層數(shù) <= 2 時(shí)足以表示所有情況.而且左括號(hào)只會(huì)打在負(fù)號(hào)的后面澜术。
那么不難表示狀態(tài):
對(duì)于每一位.不難想到有以下幾種決策:
1.不加任何括號(hào),將 (j % 2 ? -1 : 1) * a[i] 加入答案
2.加一個(gè)左括號(hào)在數(shù)之前猬腰。前提是當(dāng)前這一位是負(fù)號(hào)?將 (j % 2 ? -1 : 1) * a[i] 加入答案
3.加x個(gè)右括號(hào)在數(shù)之后?將 (j + x % 2 ? -1 : 1) * a[i] 加入答案
注意：3是一個(gè)很坑的點(diǎn)鸟废，有些情況確實(shí)需要在某個(gè)數(shù)之后加多個(gè)右括號(hào)。但是要加左括號(hào)姑荷，只需要加1個(gè)盒延。加兩個(gè)左括號(hào)無(wú)意義.
AC代碼:https://atcoder.jp/contests/arc066/submissions/17130576
