刷题笔记合集🔗

云短信平台优惠活动

问题描述

某云短信厂商为庆祝国庆，推出充值优惠活动。现给出客户预算和优惠售价序列，求客户最多可获得的短信总条数。

输入格式

第一行包含一个整数 ，表示客户预算。

第二行包含 个整数 ，其中 表示充值 元获得的短信条数。

输出格式

输出一个整数，表示最多可获得的短信条数。

样例输入1

6
10 20 30 40 60

样例输出1

70

样例输入2

15
10 20 30 40 60 60 70 80 90 150

样例输出2

210

样例解释

数据范围

题解

动态规划

这道题目本质上是一个完全背包问题。问题的关键在于如何在给定预算内，通过不同面额的充值方式获得最多的短信条数。

解题思路如下：

1. 创建一个长度为 M+1 的数组 dp，其中 dp[i] 表示预算为 i 时能获得的最大短信条数。

2. 初始化 dp = 0，表示预算为 0 时无法获得任何短信。

3. 遍历每个充值金额 i（从 1 到 n）：

   • 对于每个可能的预算 j（从 i 到 M），更新 dp[j]： dp[j] = max(dp[j], dp[j-i] + P[i])

4. 最终，dp[M] 就是在预算 M 内能获得的最大短信条数。

参考代码

• Python

def max_sms(M, P):
    """
    计算最多可获得的短信条数
    
    :param M: 预算
    :param P: 充值方案列表，P[i]表示充值i+1元可获得的短信条数
    :return: 最多可获得的短信条数
    """
    # 初始化dp数组，dp[i]表示预算为i时能获得的最大短信条数
    dp = [0] * (M + 1)
    
    # 遍历每种充值金额
    for i in range(1, len(P) + 1):
        # 从当前充值金额到预算M，更新dp数组
        for j in range(i, M + 1):
            dp[j] = max(dp[j], dp[j - i] + P[i - 1])
    
    # 返回预算M时能获得的最大短信条数
    return dp[M]

# 读取输入
M = int(input())
P = list(map(int, input().split()))

# 计算并输出结果
result = max_sms(M, P)
print(result)

• C

#include <stdio.h>
#include <stdlib.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int max_sms(int M, int* P, int n) {
    int* dp = (int*)calloc(M + 1, sizeof(int));
    
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= M; j++) {
            dp[j] = max(dp[j], dp[j - i] + P[i - 1]);
        }
    }
    
    int result = dp[M];
    free(dp);
    return result;
}

int main() {
    int M, n = 0;
    scanf("%d", &M);
    
    int P[1