砝码称重——突发奇想做的某一道题
(color{red}{mathcal{Description}})(Link) (color{red}{mathcal{Solution}})思路:(01)背包方案数 + (bitset) + 子集枚举 首先我的(dfs)菜的一匹,所以说一看这道题我就放弃了(dfs) 我们考虑子集枚举选取(n-m)个物品时的状态,然后对于每一个状态进行一次(bool)类型的(01)背包,最后统计(max)即可。 但是显然我们的复杂度会达到 [T(n) = 2^n times (n sum a_i + 3n) -> Theta(2^nnsum a_i)] 其中第一项是枚举子集的复杂度,之后是(01)背包方案数 + 扫一遍 + 清零+求出背包容量(t)的复杂度。 显然不足以(1s)过。那么我们不妨思考一个简单的优化,我们枚举状态从(1 <<(n - m - 1))开始,因为当位数小于(n - m)时,永远选不够(n-m)个。并且我们可以预处理出每个状态的(1)的个数,那么我们就会有((n) = 2^n-2^{n-m} +C_{n}^{m}cdot (n sum a_i + 3n) -> Theta(max(2^n - 2^{n-m},C_{n}^{m} cdot nsum a_i))) 好像还可以的吧,但事实上我们还可以更优,我们直接考虑用(bitset)作为(dp)数组,然后就会有(3 cdotfrac{n}{32})的检测复杂度,好像可以优化些常数。 最后我还用了 inline int max(int a,int b) {return b - (b - a & (b - a >> 31));} 的毒瘤优化,但是依旧很慢——不过这不能阻止人类否定(dfs)的一家独大。 (qwq) #include <bitset> #include <cstdio> #include <iostream> #define MAX 5000 using namespace std ; int i,j,k,d,t ; bitset <MAX> dp ; int N,M,base[MAX],Len[MAX << 8],Max,Ans ; inline int max(int a,int b) {return b - (b - a & (b - a >> 31));} int main(){ cin >> N >> M ; d = N - M,Max = (1 << N) - 1 ; for (i = 1 ; i <= N ; ++ i) cin >> base[i] ; for (i = 1 ; i <= Max ; ++ i) Len[i] = Len[i - (i & -i)] + 1 ; for (i = 1 << d - 1; i <= Max ; ++ i){ if(Len[i] == d){ dp.reset(),dp[0] = 1,t = 0 ; for (j = 0 ; j < N ; ++ j) t += (1 << j & i) ? base[j + 1] : 0 ; for (k = 0 ; k < N ; ++ k) for (j = t ; j >= base[k + 1] ; -- j) dp[j] = (1 << k & i) ? dp[j] : (dp[j] | dp[j - base[k + 1]]) ; Ans = max(Ans,(int)dp.count() - 1) ; } } cout << Ans << endl ; return 0 ; } (by Flower_ pks)(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |