EOJ-3507. 坑爹的售票机 (Easy)-白红宇

EOJ-3507. 坑爹的售票机 (Easy)

阅读量：593 次

发布时间：2019-03-11

本文共 1765 字，大约阅读时间需要 5 分钟。

优化后的文章

问题分析与解决方案

问题背景

我们需要解决一个经典的优化问题，即购买n张票时，使用最少数量的纸币。这是一种典型的动态规划问题，但需要结合贪心算法技术来解决约束条件下的问题。

问题约束

机器一次性最多能购买k张票，因此我们需要分解问题，找到购买i张票所需的最小纸币数，并将其延伸到购买n张票的情况。

解决思路

单次购买问题

首先，我们需要计算在最多购买k张票的情况下，购买i张票所需的最小纸币数。我们使用贪心算法来确定这一点。贪心算法从最大的票面开始尽可能多地使用，从而减少纸币总数。

动态规划扩展

为了处理购买n张票的情况，我们将单次购买的结果进行动态规划扩展。我们使用一个数组minv2来存储购买i张票所需的最小纸币数。通过动态转移方程和多次状态转移，逐步计算出购买n张票的最优解。

优化步骤

初始化

创建两个数组：minv1用于存储购买i张票所需的最小纸币数（i范围为1到k）；minv2用于存储购买i张票所需的最小纸币数（i范围扩展至1到n）。

单次购买计算

使用贪心算法计算minv1数组。通过遍历所有可能的i值，确定购买i张票所需的最小纸币数。

动态规划扩展

使用动态规划方法来计算minv2数组。通过递推式minv2[i] = min(minv2[i], minv2[i-j] + minv1[j])，将单次购买的结果逐步扩展到n次购买的情况。j的取值范围是从1到min(i,k)，确保不会超过购买次数限制。

代码实现

#include 
   
    using namespace std;int V[6] = { 1, 5, 10, 20, 50, 100 };#define INF 0x3f3f3f3fint main() {    int n, k, p;    cin >> n >> k >> p;    int minv1[1010] = { 0 };    int minv2[1010];    fill(minv2, minv2 + 1010, INF);    minv2[0] = 0;    minv1[0] = 0;    for (int i = 1; i <= k; ++i) {        int val = i * p;        for (int j = 5; val > 0; --j) {            if (val >= V[j]) {                minv1[i] += V[j];                val -= V[j];            }        }    }    for (int i = 1; i <= n; ++i) {        int best = INF;        for (int j = 1; j <= min(i, k); ++j) {            if (minv2[i - j] + minv1[j] < best) {                best = minv2[i - j] + minv1[j];            }        }        if (best < minv2[i]) {            minv2[i] = best;        }    }    cout << minv2[n] << endl;    return 0;}