题目描述

计算小明一年在猫咖最少花多少钱
猫咖可以办理日卡【1天】，周卡【7天】，月卡【30天】
第一行输入是日卡，周卡，月卡价格
第二行输入是小明一年内去的时间

样例

例：
20 70 150
1 2 4 7 18 20
输出：110

20 70 150
1 2 11 12 13 14 88 89 110 111 112 113
输出: 220

算法1

(dp) $O(n^2)$

dp[i]为1-i天里的最小花费

参考文献

C++ 代码

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

int dayPrice, weekPrice, monthPrice;
vector<int> inputArray;
int main() {
    cin >> dayPrice >> weekPrice >> monthPrice;
    int num;
    while (cin >> num) {
        if (num == -1) break;
        inputArray.push_back(num);
    }
    int n = inputArray.back();
    // dp[i]是以1-i天里最小的数额；
    vector<int> dp(n + 1, 0);
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (i == inputArray[count]) {
            dp[i] = dp[i - 1] + dayPrice;
            dp[i] = min(dp[i], i > 7 ? dp[i - 7] + weekPrice : weekPrice); //按天累加 与 办周卡比较
            dp[i] = min(dp[i], i > 30 ? dp[i - 30] + monthPrice : monthPrice); //按天累加 与 办月卡比较
            count++;
        }
        else {
            dp[i] = dp[i - 1]; //没有去店里
        }
    }
    cout << dp[inputArray.back()] << endl;
}