[语言月赛 202403] 大西洋船王

· · 题解

Source & Knowledge

2024 年 3 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

有 n 个任务需要完成，对于一个任务，需要派遣 1 到 m 条船。派遣一条船出一次任务的花费为 k 元，第 i 次任务派出 j 条船可以获得 a_{i,j} 元，最大化总收入。

题目分析

考察循环结构的应用。

对于第 i 次任务，使用变量 j 从 1 到 m 枚举派遣的船的数量，计算这次任务派遣 j 条船获得的收入，记录第 i 次任务能获得的最大收入。由于任务之间相互没有影响，最优情况下的总收入即每个任务能获得的最大收入之和。

注意应当使用 long long 类型变量存储答案。同时由于任务收入可能为负数，计算每个任务能获得的最大收入时应当将记录用的变量初始化为一个极小值。

long long ans=0;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
    long long sum=-1e12;//这个值必须足够小 
    for(int j=1;j<=m;j++){
        long long x;
        cin>>x;
        sum=max(sum,x-j*k);
    }
    ans+=sum;
}
cout<<ans<<'\n';

视频讲解

完整代码见视频题解