3 条题解

  • 0
    @ 2024-1-7 13:52:33

    01背包枚举状态,bitset优化时间复杂度

    int n,k;
        cin >> n >> k;
        bitset<100010>dp;
        dp[0] = 1;
        for(int i=0;i<n;i++){
            int x;
            cin >> x;
            dp|=(dp<<x);
        }
        int ans = 0;
        for(int i=0;i<=k;i++){
            if(!dp[i]){
                ans ++;
                dp|=(dp<<i);
            }
        }
        cout << ans<< endl;
    

    信息

    ID
    594
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    32
    已通过
    7
    上传者