华为OD机试【云短信平台优惠活动】

题目描述

某云短信厂商，为庆祝国庆，推出充值优惠活动。

现在给出客户预算，和优惠售价序列，求最多可获得的短信总条数

输入描述

第一行客户预算M，其中 0<=M<=100

第二行给出售价表，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

输入

18

1 2 30 40 60 84 70 80 90 150

输出

252

动态规划 完全背包问题

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

int main() {
	int sum;
	cin >> sum;
	int tmp;
	vector<int>num;//存放每种套餐对应的短信数
	vector<int>dp(sum+1,0);
	while (cin >> tmp) {
		num.push_back(tmp);
		if (cin.get() == '\n')
			break;
	}
	for (int i = 0; i < num.size(); i++) {
		for (int j = i+1; j <= sum; j++) {
			dp[j]=max(dp[j],dp[j-i-1]+num[i]);//j-(i+1)->i号套餐对应的费用为i+1
		}
	}
	cout << dp[sum];
}