CF183D

Description

传送门

Solution

算法一

令 g i , j g_{i,j} gi,j​ 表示，第 i i i 件衣服拿有 j j j 件的期望贡献。显然，我们将 g i , j g_{i,j} gi,j​ 做分组背包即可得到答案。

现在关键在于求出每一个 g i , j g_{i,j} gi,j​。注意到，若我们带了 x x x 件衣服，有 y y y 个人适合，那么最终分出去的数量就是 min ⁡ ( x , y ) \min(x,y) min(x,y)。

考虑另一个 dp \text{dp} dp。

令 f i , j , k f_{i,j,k} fi,j,k​ 表示，看到前 i i i 个人，目前第 j j j 件衣服总共适合 k k k 个人的概率。则

f i , j , k = f i − 1 , j , k − 1 × p i , j + f i − 1 , j , k × ( 1 − p i , j ) f_{i,j,k}=f_{i-1,j,k-1} \times p_{i,j}+f_{i-1,j,k} \times (1-p_{i,j}) fi,j,k​=fi−1,j,k−1​×pi,j​+fi−1,j,k​×(1−pi,j​)

g i , j = ∑ k = 0 j k × f n , i , k + j ∑ k = j + 1 n f n , i , k g_{i,j}=\sum_{k=0}^j k \times f_{n,i,k}+j\sum_{k=j+1}^n f_{n,i,k} gi,j​=k=0∑j​k×fn,i,k​+jk=j+1∑n​fn,i,k​

时间复杂度 O ( n 3 ) O(n^3) O(n3)。

算法二

我们在调试算法一中的程序时打出了 g g g，然后你就会发现: g g g 的每一行都是上凸的！

下面给出具体的证明。

g i , j + 1 − g i , j = ∑ k = 0 j + 1 k f n , i , k + ( j + 1 ) ∑ k = j + 2 n f n , i , k − ∑ k = 0 j k f n , i , k − j ∑ k = j + 1 n f n , i , k g_{i,j+1}-g_{i,j}=\sum_{k=0}^{j+1} k f_{n,i,k}+(j+1)\sum_{k=j+2}^n f_{n,i,k}-\sum_{k=0}^j k f_{n,i,k}-j\sum_{k=j+1}^n f_{n,i,k} gi,j+1​−gi,j​=k=0∑j+1​kfn,i,k​+(j+1)k=j+2∑n​fn,i,k​−k=0∑j​kfn,i,k​−jk=j+1∑n​fn,i,k​

即
g i , j + 1 − g i , j = ∑ k = j + 1 n f n , i , k g_{i,j+1}-g_{i,j}=\sum_{k=j+1}^n f_{n,i,k} gi,j+1​−gi,j​=k=j+1∑n​fn,i,k​

从而，每当 j j j 将增加 1 1 1， △ g i \triangle g_i △gi​ 就减小 f n , i , j + 1 f_{n,i,j+1} fn,i,j+1​。

现在，既然 g i g_i gi​ 有了单调性，那么我们为什么还要去跑出整个 f f f 并做背包呢？每次贪心地去选择最大贡献向下扩展就行了。

具体地说，我们维护一些 p i p_i pi​，它们初始为 g i , 1 − g i , 0 g_{i,1}-g_{i,0} gi,1​−gi,0​。每次，我们找到最大的 p p p，令其为 p x p_x px​，则我们将答案加上 p x p_x px​，然后将关于第 x x x 件衣服的 f f f 向下推一行，并将 p x p_x px​ 从 g i , t − g i , t − 1 g_{i,t}-g_{i,t-1} gi,t​−gi,t−1​ 修改为 g i , t + 1 − g i , t g_{i,t+1}-g_{i,t} gi,t+1​−gi,t​。

不难发现，此时我们只向下推了 n n n 次，每次转移的复杂度为 O ( n ) O(n) O(n)；同时，输入量为 O ( n m ) O(nm) O(nm) 级别，从而总复杂度为 O ( n ( n + m ) ) O(n(n+m)) O(n(n+m))。

其实，这里的“凸优化”的本质在于贪心——我们只需要某些特定的 g g g，从而只需要某些特定的 f f f，从而并不需要得到所有的 f i , j , k f_{i,j,k} fi,j,k​，从而将冗余操作去掉，从而将复杂度优化为最佳。

Code

马上写