皎月半洒花
2018-10-12 19:52:24
思路:
首先我的 dfs 菜的一匹,所以说一看这道题我就放弃了 dfs。
我们考虑子集枚举选取
但是显然我们的复杂度会达到
其中第一项是枚举子集的复杂度,之后是
显然不足以 1 <<(n - m - 1)
开始,因为当位数小于
好像还可以的吧,但事实上我们还可以更优,我们直接考虑用
最后我还用了
inline int max(int a, int b) {return b - (b - a & (b - a >> 31));}
的毒瘤优化,但是依旧很慢——不过这不能阻止人类否定
#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 ;
}
作者正在奋力卡常中。。。