【华为OD】C卷真题 100分：Wonderland游乐园 C语言代码实现[思路+代码]

  C++、java、python代码：

【华为OD】C卷真题 100分：Wonderland游乐园 C/C++代码实现[思路+代码]-CSDN博客

【华为OD】C卷真题 100分：Wonderland游乐园 Java代码实现[思路+代码]-CSDN博客

【华为OD】C卷真题 100分：Wonderland游乐园 python代码实现[思路+代码]-CSDN博客 

 题目描述

Wonderland是小王居住地一家很受欢迎的游乐园。Wonderland目前有4种售票方式，分别为一日票（1天）、三日票（3天）、周票（7天）和月票（30天）。

每种售票方式的价格由一个数组给出，每种票据在票面时限内可以无限制地进行游玩。例如：

小王在第10日买了一张三日票，小王可以在第10日、第11日和第12日进行无限制地游玩。

小王计划在接下来一年多次游玩该游乐园。小王计划地游玩日期将由一个数组给出。

现在，请您根据给出地售票价格数组和小王计划游玩日期数组，返回游玩计划所需要地最低消费。

输入描述

输入为2个数组：

• 售票价格数组为costs，costs.length = 4，默认顺序为一日票、三日票、周票和月票。
• 小王计划游玩日期数组为days，1 ≤ days.length ≤ 365，1 ≤ days[i] ≤ 365，默认顺序为升序。

输出描述

完成游玩计划的最低消费。

示例1

输入

5 14 30 100 1 3 5 20 21 200 202 230

输出

40

说明

根据售票价格数组和游玩日期数组给出的信息，发现每次去玩的时候买一张一日票是最省钱的，所以小王会卖8张一日票，每张5元，最低花费是40元。

     879                                                         
                                                            
              +---+                                                          
  3            |   |       ++                               +       +---|   
  |           |   | 3      +                6               +  |   +   |        +
  |      +     |   |       +         +                      +    |  +   |       +
  |      +    |   +---+    +        +        +++++          +   +  +   |        +
  |      +    | +      |   +   +----+        |   |          +   +  +   |        +
  |      +  3 | +      |   +   +    +      2 |   |     2    +   +  +   |        +
  |      +    | +      |   +   +    +        |   |          +   +  +   |        +
  |      +---+ +     |    |  |    +    ----+   |   +---+    |  |  +   |         +
  |      |     +     |    |  |    +    |       |   |   |    |  |  +   |         +
  |    1 |     +     | 8  |  |    +  1 |   |    | 1 |   | 1 |   |  +   |        +
  |      |     +     |    |  |    +    |   |    |   |   |   |   |  +   |        +
  |  +---+     +     +---+   |    ++---+    ++   +---+   +---+   |  +   |        +
  |  |         +         |   |    |         ++              |   |  |+   |        +
  |0 |         +         | 0 |  0 |         ++              | 0 |  |+   |        +
  |  |         +         |   |    |         ++              |   |  |+   |        +
  +---+         +          +-------+                       +---+| +|+   |        +
                +                                                    +   |        +
    0   1   2   3   4   5   6   7   8   9  10  11  12 + v:    w  u m    u 1 0 2 4
 

题目解析：

        使用动态规划来实现：有4种状态 1、3、7、30日票的状态，针对性的处理即可

代码实现：

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

int min(int a, int b) {
    return a < b ? a : b;
}

int main() {
    int arrCosts[4];
    for (int i = 0; i < 4; i++) {
        scanf("%d", &arrCosts[i]);
    }

    int arrDays[10000];
    int day, numDays = 0;
    while (scanf("%d", &day) == 1) {
        arrDays[numDays++] = day;
    }

    int maxDay = arrDays[numDays - 1];
    int dpArr[maxDay + 1];
    for (int i = 0; i <= maxDay; i++) {
        dpArr[i] = 0;
    }
    dpArr[0] = 0;
    int idx = 0;
    for (int i = 1; i <= maxDay; i++) {
        if (i == arrDays[idx]) {
            int b_1 = dpArr[i - 1] + arrCosts[0];
            int b_3 = (i >= 3 ? dpArr[i - 3] : 0) + arrCosts[1];
            int b_7 = (i >= 7 ? dpArr[i - 7] : 0) + arrCosts[2];
            int b_30 = (i >= 30 ? dpArr[i - 30] : 0) + arrCosts[3];
            dpArr[i] = min(min(b_1, b_3), min(b_7, b_30));
            idx++;
        } else {
            dpArr[i] = dpArr[i - 1];
        }
    }
    printf("%d\n", dpArr[maxDay]);

    return 0;
}