跳至正文

1 条题解

  • 0
    @ 2026-10-2 2:21:46

    不可达余数不参与状态转移;用上一层状态保证每件产品至多选择一次。

    #include <bits/stdc++.h>
    using namespace std;
    
    int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
    
    int n,k;cin>>n>>k;const long long NEG=LLONG_MIN/4;vector<long long>d(k,NEG);d[0]=0;while(n--){int x;cin>>x;vector<long long>b=d;for(int j=0;j<k;j++)if(d[j]!=NEG)b[(j+x)%k]=max(b[(j+x)%k],d[j]+x);d=b;}cout<<d[0]<<"\n";
    
    return 0;
    }
    
    • 1

    信息

    ID
    3974
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    0
    已通过
    0
    上传者