题目传送门 前言 今天依旧是不写高精的一天呢！（是的，这位作者又只拿了开\(LL\)的\(\color{yellow}{60}\)分） 思路描述 看到数据\(n,m\le80(30)\)就知道数组可以任性开，心理有个底后，再来看题目。 状态描述 首先肯定要来一个\(dp_{i,j}\)来表示第\(i\)次时取第\(j\)行的数。 对于每一次放置，我们要考虑到的是之前每一次都取到什么,也就是现在的头和尾分别是哪两个数。 想明白这一点，就可以描述状态了。 \(dp_{i,j,k,t}\)表示第\(i\)次时取第\(j\)行的数，对于第\(j\)行，它的行首被取了\(k\)个数，他的行尾被取了\(t...

前言 今日偶然打开\(oi-wiki\)，发现树形\(DP\)例题正好是之前在洛谷上鸽着的一道题。所以...... \(\color{red}{很高兴以这样的方式认识你，树形DP!}\) 这例题造的太好了，简直是无痛入门（感动.jpg） P1352没有上司的舞会 题目传送门 思路剖析 状态定义 \(dp_i\)表示的是以\(i\)为根节点的子树所获得的最大价值。 由于每个节点代表着一位人物，有来与不来两种状态，所以再加一维状态变量。 \(dp_{i,0}\)表示以\(i\)为根节点的子树所能获得的最大价值，且这位人物没来。\(dp_{i,1}\)则对应来了的状态。 状态转移方程 现在有个周年庆...

树状数组介绍 树状数组，顾名思义，就是树状的一维数组。 二叉树同样也可以用一维数组存储。我们以二叉树进行类比。 如图所示，图中节点的序号就是存在数组中的下标。 记父节点序号为\(p\),子节点序号为\(s\)。 则有: \(p\)\(=\)\(s\)\(/\)\(2\)(向下取整)。 左子节点\(s_{left}\)\(=\)\(p\)\(2\)。 右子节点\(s_{right}\)\(=\)\(p\)\(2+1\)。 综上可知，二叉树能用一维数组存，是由于其父子节点间存在一定关系，以至于不需要用额外的变量来表示信息。 那类比到树状数组中，可以发现： \(c\)数组即为树状数组。\(c_i...