[NOI2020]制作菜品

做法

考虑(n-1)的情况
结论1:当(m=n-1)时必然有解

证明:
最小值显然(<k),找到一个与其配对的,我们猜测若最小值与最大值和(ge k)
我们对其以(n)施归纳,那么要使最小值与最大值反复最优,这是无后效性的,故反复令最小值与最大值匹配即可
(O(nlogn))

推论:当(mge n-1)时必然有解:

证明
最大值必然(ge k),同样施归纳,可以转移到(m=n-1)的情况

结论2:当(m=n-2)时有解的充要条件是可划分为两个(m=n-1)的子问题

证明:
充分性易证
每次消掉最小的,同样施归纳

(f_{i,j,k})为前(i)个能否找到集合大小为(j)和为(k)
({d_1,d_2,cdots,d_n})转化为({d_1',d_2',cdots,d_n'})(d_i'=d_i-k)
(f_{i,k})为前(i)个能否找到和为(k),用bitset优化转移

拓展:
(m=n-p)的问题有解当且仅当能划分为(p)(m=n-1)的问题

原文地址:https://www.cnblogs.com/Grice/p/13544437.html