#P3246. 云短信平台优惠活动(200分)
-
1000ms
Tried: 145
Accepted: 13
Difficulty: 5
所属公司 :
华为od
云短信平台优惠活动(200分)
题面描述
某云短信厂商为庆祝国庆,推出充值优惠活动。给定客户的预算和不同充值金额对应的短信条数,求在这个预算下最多可以获得的短信总条数
思路
这个问题可以视为一个经典的背包问题。我们需要在有限的预算下选择最优的充值方式以最大化短信条数。具体思路如下:
-
动态规划定义:
- 定义一个一维数组
dp,其中dp[j]表示在预算为j时能够获得的最多短信条数。 - 初始时,
dp[0] = 0(预算为0时,短信条数为0),其他所有dp[j]初始化为0。
- 定义一个一维数组
-
动态规划转移方程:
- 对于每个售价
P[i](即充值金额),更新所有预算j从大到小的值:- 如果当前预算
j大于等于P[i],则更新dp[j]: [ dp[j] = \max(dp[j], dp[j - (i + 1)] + P[i]) ]
- 如果当前预算
- 这里的
dp[j - (i + 1)] + P[i]表示在预算j - (i + 1)时的短信条数,加上当前充值所能获得的短信条数。
- 对于每个售价
-
结果:
- 最后,
dp[M]中的值即为在预算M下能够获得的最多短信条数。
- 最后,
cpp
#include <iostream>
#include <vector>
#include <algorithm>
# define int long long
using namespace std;
signed main() {
int m; // 客户预算
cin >> m; // 输入预算
vector<int> p; // 存储短信条数对应的售价
int price;
// 读取短信条数对应的售价
while (cin >> price) {
p.push_back(price);
if (cin.peek() == '\n') break; // 读取到换行符则停止
}
vector<int> dp(m + 1, 0); // 动态规划数组,初始化为0,大小为 m+1
// 遍历售价列表
for (int i = 0; i < p.size(); i++) {
// p[i]条短信花费i+1元
// 从后向前更新动态规划数组
for (int j = i + 1; j <= m; j++) {
dp[j] = max(dp[j], dp[j - (i + 1)] + p[i]);
}
}
cout << dp[m] << endl; // 输出在预算m下可以获得的最大短信条数
return 0;
}
python
def main():
m = int(input()) # 输入预算
p = list(map(int, input().split())) # 读取一行的多个售价并转为整数列表
dp = [0] * (m + 1) # 动态规划数组,初始化为0,大小为 m+1
# 遍历售价列表
for i in range(len(p)):
# p[i]条短信花费i+1元
# 从后向前更新动态规划数组
for j in range(i + 1, m + 1):
dp[j] = max(dp[j], dp[j - (i + 1)] + p[i])
print(dp[m]) # 输出在预算m下可以获得的最大短信条数
if __name__ == "__main__":
main()
java
import java.util.Scanner;
public class SMSRecharge {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 输入客户预算
long m = scanner.nextLong();
scanner.nextLine(); // 读取剩余的换行符
// 读取短信条数对应的售价
String[] prices = scanner.nextLine().split(" ");
long[] p = new long[prices.length];
// 将输入的字符串转换为整数
for (int i = 0; i < prices.length; i++) {
p[i] = Long.parseLong(prices[i]);
}
// 动态规划数组,初始化为0,大小为 m+1
long[] dp = new long[(int) (m + 1)];
// 遍历售价列表
for (int i = 0; i < p.length; i++) {
// p[i]条短信花费i+1元
// 从后向前更新动态规划数组
for (int j = i + 1; j <= m; j++) {
dp[j] = Math.max(dp[j], dp[j - (i + 1)] + p[i]);
}
}
// 输出在预算m下可以获得的最大短信条数
System.out.println(dp[(int) m]);
scanner.close(); // 关闭扫描器
}
}
题目内容
某云短信厂商,为庆祝国庆,推出充值优惠活动。
现在给出客户预算,和优惠售价序列,求最多可获得的短信总条数。
输入描述
第一行客户预算 M ,其中 0≤M≤106
第二行给出售价表, P1,P2,…Pn, 其中 1≤n≤100 ,
Pi为充值 i 元获得的短信条数。1≤Pi≤1000,1≤n≤100
输出描述
最多获得的短信条数
样例1
输入
6
10 20 30 40 60
输出
70
说明
分两次充值最优, 1 元、 5 元各充一次。总条数 10 + 60 = 70
样例2
输入
15
10 20 30 40 60 60 70 80 90 150
输出
210
说明
分两次充值最优, 10 元 5 元各充一次,总条数 150 + 60 = 210