【qoj7566】题解
一：【题意】
每次选择一个区间，将区间的数统一加上实数z，求使得序列全为0的最少操作次数
二：【解法】
做前缀，题目转化为一个数+z.一个数-z
如果我们使u+=z,v-=z，则在u,v之间连边
通过一系列操作，我们最终构造了许多棵树
如果每个树的点权和为0，则一定存在使序列全为0的操作方案
此时各联通块的边数和即为操作次数
我们为什么不倒着考虑，直接构造和为0的联通块，此时生成树的边数之和即为操作次数
使得操作次数尽量小，则联通块个数需要尽量多，所以问题转化为了求划分联通块最大个数
由数据范围想到了状压dp
dp[S]:表示集合S中的元素划分联通块的最大个数
子集枚举T,dp[S]=max(1+dp[T])
此时理论时间复杂度O(3^n)
我们去掉所有0，然后采取记忆化搜索跑状压dp
虽然理论时间复杂度仍为O(3^n)，但是如果去掉0，和为0的联通快个数会少很多（并且很难卡掉）
所以状态数不会很多，实测会跑得很快
三：【代码】
（施工中。。。）