1 条题解

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

    用动态数组覆盖 N=M=100,盈利按总设备数不超过 M 求最大,正确输出每个公司的完整分配。

    #include <bits/stdc++.h>
    using namespace std;
    int main(){int n,m;cin>>n>>m;vector<vector<long long>>a(n,vector<long long>(m+1));for(auto&r:a)for(int j=1;j<=m;j++)cin>>r[j];const long long NEG=LLONG_MIN/4;vector<vector<long long>>d(n+1,vector<long long>(m+1,NEG));vector<vector<int>>take(n+1,vector<int>(m+1));d[0][0]=0;for(int i=1;i<=n;i++)for(int j=0;j<=m;j++)for(int k=0;k<=j;k++)if(d[i-1][j-k]!=NEG&&d[i-1][j-k]+a[i-1][k]>d[i][j]){d[i][j]=d[i-1][j-k]+a[i-1][k];take[i][j]=k;}int total=max_element(d[n].begin(),d[n].end())-d[n].begin();cout<<d[n][total]<<"\n";vector<int>counts(n);for(int i=n;i>0;i--){counts[i-1]=take[i][total];total-=counts[i-1];}for(int i=0;i<n;i++)cout<<i+1<<' '<<counts[i]<<"\n";}
    
    • 1

    信息

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