对于第一个测试点，我们直接暴力枚举桥梁建造情况即可。 对于剩下的测试点，我们先介绍一种优秀的做法： 我们可以建立起这样的一棵树：每一个楼房的每个楼层单独作为一个节点，楼房内部的上下楼层之间连边，楼房之间桥梁的对应楼层连边。 之后我们可以用∑_e▒〖w(e)S_1 (e)S_2 (e)〗来计算答案，其中e是树上的边，w(e)$是经过边所需的时间，S1(e),S2(e)分别是边两边子树中点的个数。 我们不妨令第1个楼房的顶层所对应的节点为树的根，则对于树上的任意一个子树，只可能存在以下三种情况： 1.完整包含了在[l,r]中的所有楼房的所有楼层，并且子树的根是这些楼房中某一个的某一层。 2.包含了第i个楼房的1,2,…,x层，并且可能完整包含了若干个i附近的楼房[l,i-1] ∪[i+1,r]，并且子树的根为第i个楼层的第x层。 3.包含了第i个楼房的x,x+1,…,hi层，并且可能完整包含了一段连续的楼房[l,r]且i ∉ [l,r]，子树的根为第i个楼房的第x层。 对于每一种情况，我们考虑使用DP来记录子树中最小的∑_e▒〖w(e)S_1 (e)S_2 (e)〗，则一共有O(n2R)种不同的状态其中R = ∑▒h_i 。 对于第一种情况的子树，我们考虑所有将[l,r]分裂成两个子段，其中一个子段可以通过子树的根节点访问到的方法。 对于第三种情况的子树，有一些[l,r]中的楼房可以经过楼房之间的桥梁从子树的根节点访问到，这些部分一定是[l,r]的一个前缀或后缀。我们尝试所有的分割[l,r]的方式，使得根节点从第i号楼的第x层移动到第x+1层。对于所有的情况，我们知道移动后子树的大小关系，于是可以计算出经过的边的贡献。 对于第二种情况的子树，根节点x可能链接了[l,r]的某些前缀或后缀。相比于尝试O(n2)种不同的方案，我们可以引入一个新的状态f:f=0表示"尝试分离前缀，但是根节点不下移"，f=1表示"尝试分离后缀，根节点下移"。 注意到不管我们什么时候在一个桥梁，我们能够到达的另一个端点都是确定的（向着选定方向移动到第一个遇到的高度不低于当前高度的楼房）。 这样子，我们在进行状态转移的时候，就可以做到O(n)，于是总体复杂度为O(n3R)。 于是，如果选手没有看出每个子树所控制的楼房是一个连续的区间，则可以使用状态压缩DP来构造一个拥有O(2nR)状态的DP做法，可以通过测试点2-4。 而如果选手看出了上述性质，但是转移的时候没有看出只会转移一个连续的前缀或后缀，则在每个状态下可以使用O(n2)的枚举来进行转移，这样复杂度为O(n4R)，可以通过测试点5-10。 对于单调的情况，桥梁只能在相邻的楼房之间建立。我们可以使用f[i][j]表示考虑到第i个楼房，它与上一个楼房的桥梁连接在j位置的最小贡献，可以简单转移。
先介绍一个优秀的做法： 首先考虑对于一个点u，我们找到它周围所有可以控制它的点的数量v，考虑点u的贡献。 首先点u和他所有可控制的点构成的集合可以构成一个合法的集合，我们称之为S。那么集合S的所有包含点u的子集显然也是一个合法集合，我们考虑它的贡献。考虑子集枚举，可以简单推出答案为∑_(s=1)^(|s|)▒〖(((|S|-1)¦(s-1))*2^s)=3^|S| -1〗。 但是这样计算会对一个集合计算多次，我们定义每一个合法的节点u为它枚举到的每一个集合的核，则显然每一个合法集合的核构成一个树。 我们用点枚举到的答案减去边枚举到的答案，就可以等于真实答案。 这个过程我们可以使用点分治在O(nlog(n))的时间内完成。 对于第一档部分分，我们可以直接暴力枚举点集。 对于第二档部分分，我们可以使用正解的思路，但是可以不使用点分治，复杂度O(n2)。
对于前20%的数据，直接手玩打表即可。 对于前40%的数据，我们使用如下一个DP来完成： 题目等价于只用由1组成的数字来抵消n，最终让n=0。设n有l位，最高位为第1位，最低位为第l位，则在第i位想要-1或+1，第i+1 … l位也需要-1或+1。 同时在第i位的变化上不可能既有-1又有+1，我们直接记录第i位的变化是-1还是+1。 用f[pos][c][x][delta(0/1)]来表示从当前最高位往低位考虑到第pos位时，前pos位还没抵消的和为c，后l … pos位都要减去一个数x，当前变化是delta时最少要用的1的数量。 则转移显然，直接记忆化dp即可。 对于前60%的数据，我们考虑优化上述dp: 记mi = 111 … 1(i个1)。则我们问题等价于：使用i的代价使x = x + mi 或x = x - mi,最小代价使x变为0。 我们用f[y][x]表示你加或减所有mi(i > y)使得剩下的数为x的最小代价。 则在转移的时候，对于f[y][x]中的每一个x，它在f[y-1][x]中至多有两种选择：假设x为非负的，这两种选择为x-kmy和x-(k+1)my其中x-kmy是非负的，x-(k+1)my是非正的。否则|x - kmy| > my则你总可以减掉(加上)一个my使得价值更小。 可以简单证明每次从f[y]转移到f[y-1]的时候至多创造O(1)个多出来的x，则总共有O(|n|)个不同的x。其中|n|是数字n的长度。 我们就得到了一个O(|n|3log|n|)的做法。其中一个|n|来自于高精度运算。 对于100%的数据，考虑优化上述高精度过程，由于mi mod mi-1 = 1，则每次变化的位数是均摊O(1)的，我们使用一个数据结构即可将其优化到O(1)，总复杂度为O(|n|2log|n|)。
T1 题解 LaTeX
先介绍一个优秀的做法：
首先考虑对于一个点 $u$，我们找到它周围所有可以控制它的点的数量 $v$，然后考虑点 $u$ 的贡献。
首先点 $u$ 和他所有可控制的点构成的集合可以构成一个合法的集合，我们称之为 $S$，那么集合 $S$ 的所有包含点 $u$ 的子集显然也是一个合法集合，我们考虑它的贡献。
考虑子集枚举，可以简单推出答案为 $\displaystyle \sum_{i=1}^{|S|}\binom{|S|}{i}2^i=3^{|S|}-1$，但是这样计算会对一个集合计算多次。
我们定义每一个合法的节点 $u$ 为它枚举到的每一个集合的核，则显然每一个合法集合的核构成一个树。我们用点枚举到的答案减去边枚举到的答案，就可以等于真实答案。
这个过程我们可以使用点分治在 $O(n\log n)$ 的时间内完成。
对于第一档部分分，我们可以直接暴力枚举点集；对于第二档部分分，我们可以使用正解的思路，但是可以不使用点分治，复杂度 $O(n^2)$。
先介绍一个优秀的做法：
首先考虑对于一个点 u，我们找到它周围所有可以控制它的点的数量 v，然后考虑点 u 的贡献。
首先点 u 和他所有可控制的点构成的集合可以构成一个合法的集合，我们称之为 S，那么集合 S 的所有包含点 u 的子集显然也是一个合法集合，我们考虑它的贡献。
考虑子集枚举，可以简单推出答案为 \displaystyle \sum_{i=1}^{|S|}\binom{|S|}{i}2^i=3^{|S|}-1，但是这样计算会对一个集合计算多次。
我们定义每一个合法的节点 u 为它枚举到的每一个集合的核，则显然每一个合法集合的核构成一个树。我们用点枚举到的答案减去边枚举到的答案，就可以等于真实答案。
这个过程我们可以使用点分治在 O(n\log n) 的时间内完成。
对于第一档部分分，我们可以直接暴力枚举点集；对于第二档部分分，我们可以使用正解的思路，但是可以不使用点分治，复杂度 O(n^2)。
@gaochunzhen AK IOI
比赛已结束。