题目描述：

商人经营一家店铺，有 ( n ) 种商品，每种商品由于仓库限制，最大持有数量为 ( item[i] )。每种商品在 ( days ) 天内的每日价格为 ( price[i][day] )。

商人可以通过对商品的买进和卖出获取利润。同一件商品可以反复买进和卖出。请计算商人在 ( days ) 天内能获取的最大利润。

解题思路：

对于每种商品，独立计算其能够获取的最大利润，最后将所有商品的利润相加。

具体而言，对于每种商品，我们需要在 ( days ) 天内决定何时买入，何时卖出，以获取最大利润。由于同一件商品可以反复买进和卖出，而且仓库有持有数量的限制，我们需要在价格上涨前买入，在价格下跌前卖出。

采用贪心算法的思想：

1. 遍历每天的价格：对于第 ( i ) 天和第 ( i+1 ) 天的价格进行比较。

   • 若第 ( i+1 ) 天的价格高于第 ( i ) 天：说明价格将上涨，应该在第 ( i ) 天尽可能多地买入商品。
   • 若第 ( i+1 ) 天的价格低于或等于第 ( i ) 天：说明价格将下跌或持平，应该在第 ( i ) 天卖出所有持有的该商品。

2. 持有量的控制：由于仓库限制，每种商品的最大持有量为 ( item[i] )。在买入时，需要检查当前持有量，确保不超过最大持有量。

3. 最后一天的处理：在最后一天，无论价格如何，都应该卖出所有持有的商品，因为之后没有机会再卖出。

时间复杂度分析：

• 对于每种商品，我们需要遍历其 ( days ) 天的价格，时间复杂度为 ( O(days) )。
• 总的时间复杂度为 ( O(n \times days) )，其中 ( n ) 为商品的种类数量。

c++

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

int main() {
    int number, days;
    cin >> number >> days;
    vector<int> item(number); // 每种商品的仓库限制
    for (int i = 0; i < number; ++i) {
        cin >> item[i];
    }

    ll total_profit = 0; // 总利润

    for (int i = 0; i < number; ++i) {
        vector<int> price(days); // 第i种商品的每日价格
        for (int j = 0; j < days; ++j) {
            cin >> price[j];
        }

        ll holdings = 0;    // 当前持有的商品数量
        ll total_cost = 0;  // 总花费
        ll total_revenue = 0; // 总收入

        for (int j = 0; j < days - 1; ++j) {
            if (price[j + 1] > price[j]) {
                // 价格将上涨，尽可能买入
                ll buy_amount = item[i] - holdings; // 能买入的最大数量
                holdings += buy_amount;
                total_cost += buy_amount * price[j];
            } else {
                // 价格将下降，卖出所有持有的商品
                total_revenue += holdings * price[j];
                holdings = 0;
            }
        }
        // 最后一天，卖出所有剩余的商品
        total_revenue += holdings * price[days - 1];
        holdings = 0;

        ll profit = total_revenue - total_cost; // 计算第i种商品的利润
        total_profit += profit; // 累加到总利润
    }

    cout << total_profit << endl; // 输出商人在这段时间内的最大利润

    return 0;
}

python

def main():
    number = int(input())  # 输入商品的数量
    days = int(input())    # 输入商人售货天数
    item = list(map(int, input().split()))  # 输入仓库限制每件商品的最大持有数量

    total_profit = 0  # 总利润

    for i in range(number):
        price = list(map(int, input().split()))  # 输入第i种商品的每日价格

        holdings = 0  # 当前持有的商品数量
        total_cost = 0  # 总花费
        total_revenue = 0  # 总收入

        for j in range(days - 1):
            if price[j + 1] > price[j]:
                # 价格将上涨，尽可能买入
                buy_amount = item[i] - holdings  # 能买入的最大数量
                holdings += buy_amount
                total_cost += buy_amount * price[j]
            else:
                # 价格将下降，卖出所有持有的商品
                total_revenue += holdings * price[j]
                holdings = 0

        # 最后一天，卖出所有剩余的商品
        total_revenue += holdings * price[days - 1]
        holdings = 0

        profit = total_revenue - total_cost  # 计算第i种商品的利润
        total_profit += profit  # 累加到总利润

    print(total_profit)  # 输出商人在这段时间内的最大利润


if __name__ == "__main__":
    main()

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int number = scanner.nextInt(); // 输入商品的数量
        int days = scanner.nextInt();   // 输入商人售货天数
        int[] item = new int[number];   // 每种商品的仓库限制
        
        for (int i = 0; i < number; i++) {
            item[i] = scanner.nextInt(); // 输入仓库限制
        }
        
        long totalProfit = 0; // 总利润
        
        for (int i = 0; i < number; i++) {
            int[] price = new int[days]; // 第i种商品的每日价格
            
            for (int j = 0; j < days; j++) {
                price[j] = scanner.nextInt(); // 输入每日价格
            }
            
            long holdings = 0; // 当前持有的商品数量
            long totalCost = 0; // 总花费
            long totalRevenue = 0; // 总收入
            
            for (int j = 0; j < days - 1; j++) {
                if (price[j + 1] > price[j]) {
                    // 价格将上涨，尽可能买入
                    long buyAmount = item[i] - holdings; // 能买入的最大数量
                    holdings += buyAmount;
                    totalCost += buyAmount * price[j];
                } else {
                    // 价格将下降，卖出所有持有的商品
                    totalRevenue += holdings * price[j];
                    holdings = 0;
                }
            }
            // 最后一天，卖出所有剩余的商品
            totalRevenue += holdings * price[days - 1];
            holdings = 0;
            
            long profit = totalRevenue - totalCost; // 计算第i种商品的利润
            totalProfit += profit; // 累加到总利润
        }
        
        System.out.println(totalProfit); // 输出商人在这段时间内的最大利润
        scanner.close();
    }
}

题目内容

商人经营一家店铺，有 $number$ 种商品，由于仓库限制每件商品的最大持有数量是 $item[index]$，每种商品的价格是 $item$_ $price[item_index][day]$。

通过对商品的买进和卖出获取利润，请给出商人在 $days$ 天内能获取的最大的利润。

注：同一件商品可以反复买进和卖出

输入描述

3 // 输入商品的数量 $number$

3 // 输入商人售货天数 $days$

4 5 6 // 输入仓库限制每件商品的最大持有数量是 $item[index]$

1 2 3 // 输入第一件商品每天的价格

4 3 2 // 输入第二件商品每天的价格

1 5 3 // 输入第三件商品每天的价格

输出描述

32 // 输出商人在这段时间内的最大利润

备注

根据输入的信息：

number = 3

days = 3

item[3] = {4, 5, 6}

item_price[3][4] = {{1, 2, 3}, {4, 3, 2}, {1, 5, 3}}

• 针对第一件商品，商人在第一天的价格是 item_price[0][0] = 1 时买入 item[0] 件，在第三天 item_price[0][2] = 3 的时候卖出，获利最大是 8；
• 针对第二件商品，不进行交易，获利最大时 0；
• 针对第三件商品，商人在第一天价格是 item_price[2][0] = 1 时买入 item[2] 件，在第二天 item_price[2][0] = 5 的时候卖出，获利最大是24；

因此这段时间商人能获取的最大利润是 8 + 24 = 32；

样例1

输入

3
3
4 5 6
1 2 3
4 3 2
1 5 2

输出

32

说明

样例2

输入

1
1
1
1

输出

0

说明