卧薪尝胆，厚积薄发。
note20180617 数位DP
Date: Sun Jun 17 08:24:43 CST 2018
In Category:
1、
$F(x)$
状态记录为之后
$F$
值的上限，这样对于不同的询问记忆化数组相同，可以一直用。
$DP$
优化：
矩阵优化：转移矩阵中
$F[i][j]$
可看作
$i$
对
$j$
的贡献。
$f_n=f_{n-1}+f_{n-2}+n$
$[f_{n-1},f_n,n,1]\to[f_n,f_n+f_{n-1}+n+1,n+1,1]$
，考虑每一位的影响即可知道
$F[i][j]$
。
$f_n=f_{n-1}+f_{n-2},s_n=s_{n-1}+f_n$
找左边和右边第一个比他大的书：建一个单调栈，一次扫描，弹栈时第一个弹不掉的就是他左边第一个比它大的，把他弹掉的就是他右边第一个比它大的。
In tag:
Timeline
About
Toolbox
Friends
Copyright © 2020
wjh15101051
ღゝ◡╹)ノ♡