贪心歌手 - 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

一个歌手准备从A城去B城参加演出

按照合同，他必须在T天内赶到
歌手不能往回走
每两座城市之间需要的天数都可以提前获知。
歌手在每座城市都可以在路边卖唱赚钱。经过调研，歌手提前获知了每座城市卖唱的收入预期: 如果在一座城市第一天卖唱可以赚M，后续每天的收入会减少D(第二天赚的钱是M - D，第三天是M-2D…)如果收入减到0就不会再少了。
歌手到达后的第二天才能开始卖唱。如果今天卖过唱，第二天才能出发

贪心的歌手最多可以赚多少钱?

输入描述

第一行两个数字 T 和 N，中间用空格隔开 T 代表总天数; N 代表路上经过N座城市; 0 < T < 1000 ,0 < N < 100

第二行N+1个数字，中间用空格隔开代表每两座城市之间耗费的时间。其总和<=T。

接下来N行，每行两个数字M和D，中间用空格隔开.

代表每个城市的收入预期。

0< M <1000, 0 < D < 100

输出描述

一个数字。代表歌手最多可以赚多少钱。以回车结束

示例1

输入：
10 2
1 1 2
120 20
90 10

输出：
540

说明：
总共10天，路上经过2座城市。 路上共花1+1+2=4天 剩余6天最好的计划是
在第一座城市待3天，在第二座城市待3天 在第一座城市赚的钱:120+100+80=300 
在第二座城市赚的钱:90+80+70=240 
一共300+240 = 540

题解

这是一个动态规划问题，需要求解在限定时间内，歌手最多可以赚多少钱。

首先，我们可以定义一个二维数组dp[i][day]，其中i表示在前i个城市中，day表示停留的天数，dp[i][day]表示在这种情况下的最大收益。

接下来，我们可以使用状态转移方程来更新dp数组。

具体来说，对于每一个城市i，我们需要考虑在这个城市停留的天数wait_day，然后更新dp[i+1][day]。

我们可以通过循环遍历wait_day和day来更新dp数组。

在这个过程中，我们需要注意每天的收益如何减少，以及在达到收益减少到0后，不再减少。

最终，我们可以在dp[n][D]中找到最大收益，其中n表示城市的数量，D表示在城市间行走后剩余的天数。

复杂度分析

该算法的时间复杂度为O(n * T * D)，其中n为城市的数量，T为总天数，D为城市间行走后剩余的天数。空间复杂度为O(n * D)。

Java

import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int t = scanner.nextInt();
        int n = scanner.nextInt();

        int sumCostTime = 0;
        int[] costTime = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            costTime[i] = scanner.nextInt();
            sumCostTime += costTime[i];
        }

        int[][] plant = new int[n][2];
        for (int i = 0; i < n; i++) {
            plant[i][0] = scanner.nextInt();
            plant[i][1] = scanner.nextInt();
        }

        // 城市可以停留的天数
        final int D = t - sumCostTime;

        // dp[i][day] 表示在前 i 个城市中，停留 day 天的最大收益
        int[][] dp = new int[n + 1][D + 1];

        for (int i = 0; i < n; i++) {
            // 每天收益, 收益减少量， 在当前城市停留的总收益
            int m = plant[i][0], d = plant[i][1], money = 0;
            for (int waitDay = 0; waitDay <= D; waitDay++) { // 在当前城市停留天数
                for (int day = waitDay; day <= D; day++) {
                    dp[i + 1][day] = Math.max(dp[i + 1][day], dp[i][day - waitDay] + money);
                }

                money += m;
                m = Math.max(0, m - d); // 每天收益减少，但不小于 0
            }
        }

        System.out.println(dp[n][D]);
    }
}

Python

t, n = map(int, input().split())

# 每两座城市之间耗费的时间
cost_time = list(map(int, input().split()))

# 代表每两座城市之间耗费的时间
plant = [tuple(map(int, input().split())) for _ in range(n)]

# 城市可以停留的世界
D = t - sum(cost_time)

# dp[i][day] 表示在前 i 个城市中，停留 day 天的最大收益
dp = [[0] * (D + 1) for _ in range(n+1)]

for i, (m, d) in enumerate(plant):
    money = 0  # 在当前城市的收益
    for wait_day in range(D + 1):  # 在当前城市停留天数
        for day in range(wait_day, D + 1):
            dp[i+1][day] = max(dp[i+1][day], dp[i][day - wait_day] + money)

        # 当获当前城市的收益
        money += m
        # 每天收益减少
        m = max(0, m - d)

print(dp[n][D])

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t, n;
    cin >> t >> n;

    int         sum_cost_time = 0;
    vector<int> cost_time(n + 1);
    for (int i = 0; i <= n; i++) {
        cin >> cost_time[i];
        sum_cost_time += cost_time[i];
    }

    vector<pair<int, int>> plant(n);
    for (int i = 0; i < n; i++) cin >> plant[i].first >> plant[i].second;

    // 城市可以停留的天数
    const int D = t - sum_cost_time;

    // dp[i][day] 表示在前 i 个城市中，停留 day 天的最大收益
    vector<vector<int>> dp(n + 1, vector<int>(D + 1, 0));

    for (int i = 0; i < n; i++) {
        // 每天收益, 收益减少量， 在当前城市停留的总收益
        int m = plant[i].first, d = plant[i].second, money = 0;
        for (int wait_day = 0; wait_day <= D; wait_day++) {   // 在当前城市停留天数
            for (int day = wait_day; day <= D; day++) {
                dp[i + 1][day] = max(dp[i + 1][day], dp[i][day - wait_day] + money);
            }

            money += m;
            m = max(0, m - d);   // 每天收益减少，但不小于 0
        }
    }

    cout << dp[n][D] << endl;

    return 0;
}