题解：P14751 醒来之后，我回到了汰换系统更新前

yushyi · 2025-12-14 17:03:55 · 题解

思路

看到这题，我就想到应该用枚举去做。那么应该根据什么枚举就是个问题。如果根据天数进行枚举，那么我会发现，一天售出物品的数量是不定的。那么就只能根据物品进行枚举了，也就是说看每一个物品在哪一天被售出。如果一次枚举某个物品在哪一天售出的话呢复杂度为 O(m^n)，这显然会超时。

那么可以在这里做一个简单的贪心，能卖的一些贵的肯定尽量卖贵些，当然如果在无论哪一天售出该商品都会亏本的话呢，我们就不卖此物品了，这样复杂度为 O(n \times m)。

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 110;
int n,m,v[N],w[N][N];

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++){
        scanf("%d",&v[i]);
    }
    for(int i = 1;i <= m;i++){
        for(int j = 1;j <= n;j++){
            scanf("%d",&w[i][j]);
        }
    }
    int ans = 0;
    for(int i = 1;i <= n;i++){
        int mx = 0;
        for(int j = 1;j <= m;j++){
            mx = max(mx,w[j][i]-v[i]);
        }
        // 如果mx的值为0，则说明在无论哪一天售出该商品都不会赚到钱，则不卖此商品，收益为0，因此此处不需要特判
        ans += mx;
    }
    printf("%d",ans);
    return 0;
}