建议加强数据,无剪枝的dfs轻松水过
查看原帖
建议加强数据,无剪枝的dfs轻松水过
1074084
asd890123楼主2024/6/9 09:15

复杂度应该是2^n(这里表示次幂而不是异或),极端值约为1e9,但还能19ms过#5(最长的点),所以应该加强数据。

#include <iostream>

int n,v,ans = 0x7fffffff,box[35];

void dfs(int x,int v){
    
    ans = std::min(ans,v);
    if (x > n) return;
    dfs(x + 1,v);
    if (box[x] <= v) dfs(x + 1,v - box[x]);
    
}//正在考虑是否选择第x个物品,当前箱子剩余体积为v

int main(){
    
    std::ios::sync_with_stdio(0);
    std::cin.tie(0),std::cout.tie(0);
    
    std::cin >> v >> n;
    for (int i = 1;i <= n;i++) std::cin >> box[i];
    dfs(1,v);
    std::cout << ans << '\n';
    
    return 0;
}
2024/6/9 09:15
加载中...