约束条件下最优化问题

Published: by Creative Commons Licence

  • Tags:

未知数区间约束问题

题目1:给定$n$条非负未知数$x_1,\ldots,x_n$,以及$m$个条件。第$i$个条件选择一个区间$[l_i,r_i]$以及一个非负数$c_i$,并要求$\sum_{j=l_i}^{r_i}x_i\leq c_i$。在上述约束条件下,我们希望最大化$\sum_{i=1}^nx_i$,如果结果是无穷则输出$-1$。其中$1\leq n,m\leq 10^6$

这个问题可以这样来解决。首先我们可以发现在最优情况下$x_1$一定会取到最大,如果$x_1$未取到最大,则一种情况是$x_2,\ldots,x_n$都是$0$,这时候我们可以让$x_1$增加$1$,这与当前是最优情况相悖。第二种情况是存在一个最小的下标$j$,满足$1\lt j$且$x_j>0$,这时候我们让$x_j$减少$1$,同时让$x_1$增加$1$,重复这个过程直到$x_1$达到最大为止,可以发现这个过程不会导致任意约束条件被破坏。

因此具体的做法按照下标从小到大处理$x_i$,同时维护一个平衡树,平衡树中按照约束$c$排序,存储所有覆盖了$x_i$的约束。之后我们选择最小的约束$y$,并将$x_i$设置为$y$,并将平衡树中所有约束全部减少$y$。

至于无穷,如果我们发现某个未知数没有被约束,则结果为无穷。

这个做法的时间复杂度为$O((n+m)\log_2m)$。

题目2:给定$n$条非负未知数$x_1,\ldots,x_n$,以及$m$个条件。第$i$个条件选择一个区间$[l_i,r_i]$以及一个非负数$c_i$,并要求$\sum_{j=l_i}^{r_i}x_i\geq c_i$。在上述约束条件下,我们希望最小化$\sum_{i=1}^nx_i$。其中$1\leq n,m\leq 10^6$

类似问题1,这个问题也可以贪心解决。首先我们可以发现在最优情况下$x_1$一定会取到最小,如果$x_1$未取到最小,这时候我们让$x_2$增加$1$,同时让$x_1$减少$1$,重复这个过程直到$x_1$达到最小为止,可以发现这个过程不会导致任意约束条件被破坏。

这道题目的做法,就是遍历下标,当我们遍历到$i$的时候,找到所有右边界恰好为$i$的约束,将$x_i$设置为最大的约束值。这个过程可以通过维护前缀和来优化,总的时间复杂度为$O(n+m)$。

负重问题

题目1:给定$n$只骆驼,$m$条桥,骆驼需要经过这些桥。其中第$i$只骆驼的重量为$w_i$,第$i$个桥的长度为$l_i$,负重为$v_i$。你可以任意调整骆驼的先后顺序,并且为两只相邻骆驼赋予一个距离。现在希望骆驼队伍能顺利通过所有桥的前提下,最小化队伍头部骆驼和尾部骆驼的距离。如果有若干只骆驼之间最大距离小于$l_i$,且它们的总重量超过$v_i$,则它们不能通过桥$i$。其中$1\leq 8\leq n, 1\leq m\leq 10^5, 1\leq w_i,l_i,v_i\leq 10^9$。

原题

一开始想的是贪心让相邻骆驼距离尽可能接近,利用二分,对于每个排列的时间复杂度为$O(nm\log_210^9)$,但是可以发现实际上我们可以把二分去掉,时间复杂度为$O(nm)$,但是加上排列后时间复杂度为$O(n!nm)$,这个显然太慢了。

我们可以发现对于排列$1,2,\ldots,n$,如果某个距离分配无法通过,则必定存在一个区间$[l,r]$,以及某条桥$i$,区间中的骆驼的总距离小于$l_i$,但是总重量大于$v_i$。因此如果区间都满足桥的约束,则就能顺利通过所有桥。

事实上虽然$m$很大,但是可以发现每个区间$[l,r]$仅存在一个最大的约束条件,而如果通过预处理$m$条桥(桥的负重越大,长度也越大),我们这里可以$O(\log_2m)$得到具体的约束条件。这部分实际上是未知数区间约束问题的第二题,可以在$O(n^2\log_2m)$时间复杂度内解决。

总的时间复杂度为$O(n!n^2\log_2m)$。

独立集问题

题目1:给定$n$个点,其中第$i$个点的位置为$(x_i,y_i)$,它的权重为$w_i$,要求选择一组点,要求这些点都不同行,也不同列,问最大权重之和为多少。

最简单就是进行位压DP,时间复杂度为$O(n2^n)$。这里可以使用meet in middle技巧,可以优化到$O(n2^{\frac{n}{2}})$。如果$n$很小还是不错的。

还可以用最大权拟阵交算法解决这个问题,时间复杂度大致为$O(n^4)$。具体的思路:将$x$当成一种颜色,我们现在定义独立集为不同颜色的元素组成的集合,可以发现这一定义满足拟阵的要求。对于$y$同样处理。满足条件的选择一定同时是两个拟阵中的独立集,于是问题就变成了最大权拟阵交。

还可以用最大权二分图匹配解决这个问题。对应到二维点,可以发现每一行最多取一个元素,每一列最多可以取一个元素。建立一个二分图,一侧顶点代表可能的横坐标,一侧顶点代表可能的纵坐标,对于球$i$,可以对应的加入一条边$(x_i,y_i)$,其权重为球的$w_i$。可以发现满足条件的一种选择方案与二分图的匹配是一一对应的,因此现在的问题变成了求二分图的最大权匹配。这个用费用流跑的话,可以做到$O(n^2\log_2n)$。

题目2:给定$n$个点,对于$i,j$,如果有$|i-j|=a$或$|i-j|=b$,则在两个顶点之间连一条边,否则就不连边。要求计算最大独立集的大小。其中$1\leq n\leq 10^{18}$,$1\leq a,b\leq 22=M$。

一道题目

这道题目实际上没有太大价值,但是证明用到的技术很不错。

考虑$p=a+b$,记$r=n\mod p$。考虑最优解的二进制表示形式,我们把它划分为长度为$r$和$p-r$交替的序列$A_1B_1A_2B_2\ldots A_{k-1}B_{k-1}A_{k}$。之后我们不妨设$A_iB_i$是$1$出现总数最大的连续两个元素(还有可能是$B_iA_{i+1}$,证明方法类似)。之后我们可以很安全的将$A_1B_1,A_2B_2,\ldots,A_{i-1}B_{i-1}$替换为多个$A_iB_i$,并将$B_{i+1}A_{i+2},B_{i+2}A_{i+3},\ldots,B_{k}A_{k+1}$替换为多个$B_iA_i$。此时我们的结果是不会变差的,而且由于$A_{i+1}$中的$1$的数目不超过$A_i$中$1$的数目,因此我们同时将$A_{i+1}$替换为$A_i$。此时我们可以发现得到了一个不逊色最优解的答案$A_iB_iA_iB_i\ldots A_iB_iA_i$。

上面的部分证明一定存在一个最优解,其周期为$p$。接下来我们只需要枚举所有可能的前$p$个选择。这里我们可以直接用meet in middle来做,时间复杂度为$O(M2^M)$,当然更好的方法是发现我们只需要决定前$b$个元素,后$a$个元素可以直接贪心选择(这里假设$b\geq a$),时间复杂度是相同的,也是$O(M2^M)$。