王者荣耀虎年充值—

整活简介

今天是农历除夕，王者荣耀一年一度的 ~~割韭菜~~ 年限皮肤又上场了。

打开游戏，进入充值页面，开冲！

嗯？等等，好像要破费？！

虽然APP Store有充值赠送机制，但当我需要的目标数额多起来时，怎么获取最优化的充值方案呢？似乎是个有趣的问题 😼

所谓 最优化的充值方案 ，即是指两种情况：

花费最少的钱，获取目标数额的点券；
在一定量的花销下，获取最多的点券。

这两种情景不一样哈！第一个是在满足购买需求的情况下尽可能少地花钱！第二个是在预算有限的情况下尽可能多地买到点券！

场景一、购买一定点券，计算最少花销

场景一就是当我们需要一定数量的点券时，计算最少的花销是多少！这个场景很有意义！因为在充钱的时候，大多数情况就是这个场景！我们不会去考虑这次要冲多少钱，而是首先考虑这次要买的是什么东西。

既然文章标题都已经点明了我的用意，那就直接从DP的角度开始思考了 😏

令 dp[i] 表示 购买 i 点券的最少花销 ，那么对于目标点券 i ，它可以由上图中所有可能的方案组成。例如我们需要购买 1430 点券，那么我们可以花费若干个 1￥ 购买若干份 10点券 ，也可以花费两个 68￥ 购买两份 715(680+35)点券 。唯一的限制是，不能使用比 i 更大的购买方案，例如我们需要 1430 点券，那就不能花费 648￥ 去买到六千多点券，不然就很浪费！

既然要使用DP，那么我们得到的状态转移方程应该是什么呢？

这是个很简单的问题！假如我们使用的购买方案是 m ， cost[m] 表示使用 m 号购买方案 花费的RMB ，gain[m] 表示使用 m 号购买方案 获得的点券 ，而 dp[i] 仍然是 购买 i 点券的最少花销 ，那么： $dp[i] = min(dp[i], dp[i - gain[m]] + cost[m])$ 其实就是：假如我们选择了方案 m ，获得了gain[m] 的点券，花掉了 cost[m] 的钱，还要继续获得 i - gain[m] 的点券，这个 i - gain[m] 点券的最少花销应该是此前已经计算过的了！那么总的花销就是 dp[i - gain[m]] + cost[m] 啦！

我们要考虑的是最优的方案，只要要把所有符合条件的方案 m 循环一遍即可。

根据以上的分析，开始真正的DP过程，需要注意的是：

可以看到APP Store里面所有的购买方案中，即便考虑了赠送的点券，获取到的点券也都是 5 的倍数。
目标点券有可能无法恰好获取，此时必须容许一定程度的上溢，例如我只希望购买 888 点券，但这个数额不是 5 的倍数，因此我可能需要购买 890 的点券。

void minCostToGetTargetPoints(int targetPoints)
{
    int i;
    vector<int> dp(targetPoints + 61, DP_MAX);
    dp[10] = 1;  // 10 Points 1 RMB
    dp[0] = 0;

    for (i = 10; i <= targetPoints + 60; i += 5)
    {
        int m = 0;
        while (gain[m] <= i)
        {
            dp[i] = min(dp[i], dp[i - gain[m]] + cost[m]);
            m++;
        }
    }

    printResultByTargetPoints(dp, targetPoints);

    return ;
}

void printResultByTargetPoints(vector<int>& dp, int targetPoints)
{
    int i = targetPoints;
    // 首先要找到第一个可用的方案
    while (dp[i] == DP_MAX) i++;
    // 之后开始打印上溢 60 点券之内的方案
    while (i < dp.size())
    {
        if (dp[i] == DP_MAX)
        {
            i += 5;
            continue;
        }
        cout << "Cost " << dp[i] << " yuan to get " << i << " points.\n";
        i += 5;
    }

    return ;
}

在上面这部分代码中，有几个细节：

允许上溢 60 点券，即我本来可能需要买 220 点券，但可以计算到购买 280 点券的最优解；
因为能买到的点券额度一定是 5 的倍数，因此DP时直接将 i += 5 ；
对于无解的情况，例如购买 13 个点券这种情况， dp[13] 一定等于原始的 DP_MAX ，这种情况正如此前所说，要发生上溢，也就是在输出答案的时候先把 i 一直往上增加，直到 dp[i] != DP_MAX 为止！

直接尝试执行一下！

#define DP_MAX 0xffff

vector<int> cost = { 1, 6, 45, 68, 118, 198, 348, 648 };
vector<int> gain = { 10, 60, 475, 715, 1240, 2100, 3690, 6868 };

int main() {
    minCostToGetTargetPoints(2140);
}

/*
执行完成，耗时：0 ms
Cost 202 yuan to get 2140 points.
Cost 204 yuan to get 2145 points.
Cost 203 yuan to get 2150 points.
Cost 205 yuan to get 2155 points.
Cost 204 yuan to get 2160 points.
Cost 206 yuan to get 2165 points.
Cost 205 yuan to get 2170 points.
Cost 207 yuan to get 2175 points.
Cost 206 yuan to get 2180 points.
Cost 208 yuan to get 2185 points.
Cost 207 yuan to get 2190 points.
Cost 209 yuan to get 2195 points.
Cost 208 yuan to get 2200 points.
*/

难受了！这是什么输出啊？？我只知道要获得目标点券最少需要多少元，但是程序没告诉我具体的充值方案！

看来需要一个额外的变量来告诉我最近的一次充值是多少数额，然后我逐渐往回递推，获得总的充值方案。

新增一个小功能，要额外花费不少代码行：

void minCostToGetTargetPoints(int targetPoints)
{
    int i;
    vector<int> dp(targetPoints + 61, DP_MAX);
    vector<int> lastTopup(targetPoints + 61, DP_MAX);
    dp[10] = 1;  // 10 Points 1 RMB
    dp[0] = 0;

    for (i = 10; i <= targetPoints + 60; i += 5)
    {
        int m = 0;
        while (gain[m] <= i)
        {
            if (dp[i] >= dp[i - gain[m]] + cost[m])
            {
                dp[i] = dp[i - gain[m]] + cost[m];
                // 新增：保存一下最后一次充值购买的方案
                lastTopup[i] = m;
            }
            m++;
        }
    }

    printResultByTargetPoints(dp, lastTopup, targetPoints);

    return ;
}

void printResultByTargetPoints(vector<int>& dp, vector<int>& lastTopup, int targetPoints)
{
    int i = targetPoints;
    // 首先要找到第一个可用的方案
    while (dp[i] == DP_MAX) i++;
    // 之后开始打印上溢 60 点券之内的方案
    while (i < dp.size())
    {
        if (dp[i] == DP_MAX)
        {
            i += 5;
            continue;
        }
        cout << "Cost " << dp[i] << " yuan to get " << i << " points.\n";
        cout << "The method is : \n\tcost(￥)\tpoints\n";
        for (int tmp = i; tmp > 0; )
        {
            int m = lastTopup[tmp];
            cout << "\t" << cost[m] << "\t\t" << gain[m] << "\n";
            tmp -= gain[m];
        }
        i += 5;
    }
}

执行一下！

#define DP_MAX 0xffff

vector<int> cost = { 1, 6, 45, 68, 118, 198, 348, 648 };
vector<int> gain = { 10, 60, 475, 715, 1240, 2100, 3690, 6868 };

int main() {
    minCostToGetTargetPoints(2140);
}

/*
执行完成，耗时：0 ms
Cost 202 yuan to get 2140 points.
The method is : 
    cost(￥)    points
    198        2100
    1        10
    1        10
    1        10
    1        10
Cost 204 yuan to get 2145 points.
The method is : 
    cost(￥)    points
    68        715
    68        715
    68        715
Cost 203 yuan to get 2150 points.
The method is : 
    cost(￥)    points
    198        2100
    1        10
    1        10
    1        10
    1        10
    1        10
Cost 205 yuan to get 2155 points.
The method is : 
    cost(￥)    points
    68        715
    68        715
    68        715
    1        10
Cost 204 yuan to get 2160 points.
The method is : 
    cost(￥)    points
    198        2100
    6        60
======= 此处省略若干行 =======
*/

从上面这个例子的输出可以看到：同样的 204￥ ，有的方案可以买到 2145 点券，而有的能买到 2160 点券！差了一块多！因此我们不能只打印目标点券的最优解，往上多打印几个，可能发现用相同的钱可以买到更多点券，何乐不为呢 😹

场景二、固定一定花销，购买最多点券

场景一是比较常见的，至于场景二，手头比较拮据的时候用吧！

这个场景就是个典型的 完全背包问题 而已：令 dp[j] 表示花费 j 元钱能买到的最多点券，那么对于所有可行的方案 m ，转移方程就是： $dp[i] = max(dp[i], dp[i - cost[m]] + gain[m])$ 其实两个场景思路差不多，直接上代码！

void maxPointsByMaxCost(int maxCost)
{
    int j = 0;
    vector<int> dp(maxCost + 1, 0);
    vector<int> lastPurchase(maxCost + 1, 0);

    for (j = 0; j <= maxCost; j++)
    {
        int m = 0;
        while (cost[m] <= j)
        {
            if (dp[j] <= dp[j - cost[m]] + gain[m])
            {
                dp[j] = dp[j - cost[m]] + gain[m];
                lastPurchase[j] = m;
            }
            m++;
        }
    }

    printResultByMaxCost(dp, lastPurchase, maxCost);

    return ;
}

void printResultByMaxCost(vector<int>& dp, vector<int>& lastPurchase, int& maxCost)
{
    cout << "You can get " << dp[maxCost] << " points using " << maxCost << " yuan.\n";
    cout << "The method is: \n\tCost(￥)\tPoints\n";
    for (int tmp = maxCost; tmp > 0; )
    {
        int m = lastPurchase[tmp];
        cout << "\t" << cost[m] << "\t" << gain[m] << "\n";
        tmp -= cost[m];
    }

    return ; 
}

执行一下：

#define DP_MAX 0xffff

vector<int> cost = { 1, 6, 45, 68, 118, 198, 348, 648 };
vector<int> gain = { 10, 60, 475, 715, 1240, 2100, 3690, 6868 };

int main() {
    // minCostToGetTargetPoints(2135);
    maxPointsByMaxCost(499);
    maxPointsByMaxCost(200);
    maxPointsByMaxCost(20);
}

/*
执行完成，耗时：0 ms
You can get 5280 points using 499 yuan.
The method is: 
    Cost(￥)    Points
    198    2100
    198    2100
    45    475
    45    475
    6    60
    6    60
    1    10
You can get 2120 points using 200 yuan.
The method is: 
    Cost(￥)    Points
    198    2100
    1    10
    1    10
You can get 200 points using 20 yuan.
The method is: 
    Cost(￥)    Points
    6    60
    6    60
    6    60
    1    10
    1    10
*/

总的代码

#define DP_MAX 0xffff

vector<int> cost = { 1, 6, 45, 68, 118, 198, 348, 648 };
vector<int> gain = { 10, 60, 475, 715, 1240, 2100, 3690, 6868 };

void printResultByTargetPoints(vector<int>& dp, vector<int>& lastTopup, int targetPoints);

void minCostToGetTargetPoints(int targetPoints)
{
    int i;
    vector<int> dp(targetPoints + 61, DP_MAX);
    vector<int> lastTopup(targetPoints + 61, DP_MAX);
    dp[10] = 1;  // 10 Points 1 RMB
    dp[0] = 0;

    for (i = 10; i <= targetPoints + 60; i += 5)
    {
        int m = 0;
        while (gain[m] <= i)
        {
            if (dp[i] >= dp[i - gain[m]] + cost[m])
            {
                dp[i] = dp[i - gain[m]] + cost[m];
                // 新增：保存一下最后一次充值购买的方案
                lastTopup[i] = m;
            }
            m++;
        }
    }

    printResultByTargetPoints(dp, lastTopup, targetPoints);

    return ;
}

void printResultByTargetPoints(vector<int>& dp, vector<int>& lastTopup, int targetPoints)
{
    int i = targetPoints;
    // 首先要找到第一个可用的方案
    while (dp[i] == DP_MAX) i++;
    // 之后开始打印上溢 60 点券之内的方案
    while (i < dp.size())
    {
        if (dp[i] == DP_MAX)
        {
            i += 5;
            continue;
        }
        cout << "Cost " << dp[i] << " yuan to get " << i << " points.\n";
        cout << "The method is : \n\tcost(￥)\tpoints\n";
        for (int tmp = i; tmp > 0; )
        {
            int m = lastTopup[tmp];
            cout << "\t" << cost[m] << "\t\t" << gain[m] << "\n";
            tmp -= gain[m];
        }
        i += 5;
    }
}

void printResultByMaxCost(vector<int>& dp, vector<int>& lastPurchase, int& maxCost);
void maxPointsByMaxCost(int maxCost)
{
    int j = 0;
    vector<int> dp(maxCost + 1, 0);
    vector<int> lastPurchase(maxCost + 1, 0);

    for (j = 0; j <= maxCost; j++)
    {
        int m = 0;
        while (cost[m] <= j)
        {
            if (dp[j] <= dp[j - cost[m]] + gain[m])
            {
                dp[j] = dp[j - cost[m]] + gain[m];
                lastPurchase[j] = m;
            }
            m++;
        }
    }

    printResultByMaxCost(dp, lastPurchase, maxCost);

    return ;
}

void printResultByMaxCost(vector<int>& dp, vector<int>& lastPurchase, int& maxCost)
{
    cout << "You can get " << dp[maxCost] << " points using " << maxCost << " yuan.\n";
    cout << "The method is: \n\tCost(￥)\tPoints\n";
    for (int tmp = maxCost; tmp > 0; )
    {
        int m = lastPurchase[tmp];
        cout << "\t" << cost[m] << "\t" << gain[m] << "\n";
        tmp -= cost[m];
    }

    return ; 
}

int main() {
    minCostToGetTargetPoints(2135);
    maxPointsByMaxCost(499);
    maxPointsByMaxCost(200);
    maxPointsByMaxCost(20);
}

我用了LeetCode的 playground 功能，因此这个代码就没有头函数之类了~

在最后，今年我希望购买鲁班和孙膑的皮肤，可能还需要进阶一下战令！总共需要 1430+710+388 = 2528 点券。我的程序告诉我：

/*
执行完成，耗时：0 ms
Cost 241 yuan to get 2530 points.
The method is : 
    cost(￥)    points
    198        2100
    6        60
    6        60
    6        60
    6        60
    6        60
    6        60
    6        60
    1        10
Cost 241 yuan to get 2535 points.
The method is : 
    cost(￥)    points
    45        475
    45        475
    45        475
    45        475
    45        475
    6        60
    6        60
    1        10
    1        10
    1        10
    1        10
Cost 242 yuan to get 2540 points.
The method is : 
    cost(￥)    points
    198        2100
    6        60
    6        60
    6        60
    6        60
    6        60
    6        60
    6        60
    1        10
    1        10
Cost 242 yuan to get 2545 points.
The method is : 
    cost(￥)    points
    45        475
    45        475
    45        475
    45        475
    45        475
    6        60
    6        60
    1        10
    1        10
    1        10
    1        10
    1        10
===== 省略若干行 =====
*/

看来我得花掉 241￥ ，真是一笔大数目 😿

同时，我的程序还告诉我，241元最多可以获取到：

/*
执行完成，耗时：0 ms
You can get 2535 points using 241 yuan.
The method is: 
    Cost(￥)    Points
    45        475
    45        475
    45        475
    45        475
    45        475
    6        60
    6        60
    1        10
    1        10
    1        10
    1        10
You can get 2575 points using 243 yuan.
The method is: 
    Cost(￥)    Points
    198        2100
    45        475
*/

诶？多花2块钱，即243元，能够多获取 40 点券？

我先去充钱了朋友们~

mpv945commentedover 2 years ago

添加图片，如果使用外部图床的http链接。图片无法点击放大，你那边怎么解决的？

SGS4evercommentedover 2 years ago

@mpv945
添加图片，如果使用外部图床的http链接。图片无法点击放大，你那边怎么解决的？

我的博客没有使用图床，所以没办法帮到你~

Celetherincommentedover 2 years ago

您好，我也是使用的stack主题，我在照着您的方法添加返回顶部按钮时，遇到了按钮虽然出现、也能够点击，但无法实现实际上的返回顶部功能的问题，我没有任何的代码知识，不知道您有没有解决方法？
另外，也是想提醒一下其他需要这篇教程的朋友，最新版的stack主题，添加返回按钮的组件应该在layouts/partials/sidebar/right.html, 在layouts/_default/single.html中添加代码会导致出现两个右边栏。

jsjcjsjccommentedover 2 years ago

请教一下博主,如何优雅的给stack主题添加广告哈?
我只想在左或者右侧边栏底部,或者每篇文章底部添加一个小小的广告,但是默认似乎的满屏广告哈~~
感谢

按照我的理解，可能有几个方法，供参考： 1、在任意HTML文件里添加广告元素，然后在CSS文件里设置广告元素的样式，把它放到你想要的位置； 2、利用Stack主题现有的页面结构，在特定的HTML文件里添加广告元素，这样这些元素就会受主题样式的限制而出现在页面的特定位置；例如我在这篇文章 Hugo Stack主题更新小记 (xrg.fj.cn) 里，在页面右侧添加了返回顶部按钮由于Stack主题已经更新多版，并且我暂时没有时间研究最新的主题源码，这里只能给出一些操作思路而无法给出具体的操作指导，望理解。 1092417672 ***@***.***  

…

------------------ 原始邮件 ------------------ 发件人: "SGS4ever/BlogComments" ***@***.***>; 发送时间: 2023年2月25日(星期六) 晚上10:36 ***@***.***>; ***@***.******@***.***>; 主题: Re: [SGS4ever/BlogComments] 错题本 | LeetCode1610. 可见点的最大数目 (Issue #44) 请教一下博主,如何优雅的给stack主题添加广告哈? 我只想在左或者右侧边栏底部,或者每篇文章底部添加一个小小的广告,但是默认似乎的满屏广告哈~~ 感谢 — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you authored the thread.Message ID: ***@***.***>

ClimbingMousecommentedalmost 2 years ago

你好，按照你的方法设置页面载入动画，这个动画不会停止咋办啊

46fafacommentedalmost 2 years ago

博主你好，请问一下主页布局修改哪里的代码如何作用于整个网页，我发现修改后的布局只存在主页和前两篇文章，其他部分还是没修改的样子

4kohakunushicommentedover 1 year ago

你好，关于左侧栏图标高亮我这里存在一些问题想请教你。我取消了原本主页直接抓取post的内容在中间显示的版块，这个部分改成了其他东西，与此同时新增了一个抓取post信息的与links、search等目录并列的一个目录，现在的问题是这些部分虽然都能正常显示，但是对应的抓取post的那个目录无法选中以后高亮，应该修改增加什么才能让它也可以选中后高亮呢？

SGS4evercommentedover 1 year ago

首先我只能基于本文使用的Stack版本来尝试解答，因为没看过当前的Stack主题的代码～
我重新翻了下此前写的关于高亮的内容，理论上只要你的post页面的标题在menu配置中即可高亮。如果post页面是你站点的根路径，那应该可以参考我的文章里写的方法，修改下active的触发逻辑～

@4kohakunushi
你好，关于左侧栏图标高亮我这里存在一些问题想请教你。我取消了原本主页直接抓取post的内容在中间显示的版块，这个部分改成了其他东西，与此同时新增了一个抓取post信息的与links、search等目录并列的一个目录，现在的问题是这些部分虽然都能正常显示，但是对应的抓取post的那个目录无法选中以后高亮，应该修改增加什么才能让它也可以选中后高亮呢？

sansan-cccommentedabout 1 month ago

感谢博主的建站帖子，有很大的帮助。