[vp]ARC059

https://atcoder.jp/contests/arc059/

My Submissions

赛时AC : CD

E,F两道dp，我不会dp石锤了

C:平均数 四舍五入

D:贪心检查长度为2或3的子串。

E:看起来像毒瘤计数之类的，仔细分析其实是个dp。

\(f_{i,j}\)表示前\(i\)个小朋友拿了\(j\)个糖果

那么\(f_{i,j}=\sum{f_{i-1,j-k} \times \sum_{p=A_i}^{B_i}{p^k}}\)

后面的式子可以用前缀和优化到\(O(n^3)\)

F: 学到的：用当前状态更新其他状态有时候会好理解一些。

\(f_{i,j}\)表示用\(j\)次操作形成了\(i\)个字符

敲\(0\)和\(1\)：\(f_{i+1,j+1} + = f_{i,j}\)

敲退格：第\(i\)个字符怎么敲都行，两种选择，如果\(i>0\)，\(f_{i-1,j+1} += 2 \times f_{i,j}\)

否则\(i=0\)，\(f_{0,j+1} + = f_{0,j}\)

总结：多做\(dp\)