题目:AcWing 4741.魔法百合井

森林里有一口很深的魔法井，井中有 L 朵百合花。

你带着一个大空篮子和足够多的硬币来到了井边。
这个井有魔力，向里面投入硬币可以发生神奇的事情：

如果你向井里一次性投入 1 个硬币，井就会发动魔法，将一朵百合花扔进你的篮子里。
如果你向井里一次性投入 4 个硬币，井就会发动魔法，统计并记录到目前为止，已经扔进你的篮子里的百合花的数量。
如果你向井里一次性投入 2 个硬币，井就会发动魔法，将等同于上次记录数量的百合花扔进你的篮子里。
有一点需要特别注意，如果你向井里一次性投入 1 个或 2 个硬币后，井中已经没有足够的百合花扔给你了，那么井就不会发动任何魔法，也不会扔给你任何百合花（钱白花了）。

请你计算，为了将所有百合花都收入篮中，所需要花费的最少硬币数量。

自己尝试的错误做法

可以发现这样选不出最优的开始倍增的位置,原理我也不清楚,反正模拟下案例发现这样暴力模拟确实做不出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

//增加一朵鲜花需要1
//对当前持有鲜花倍增需要4+2=6
//对上一次持有的鲜花数进行倍增需要2

// 当篮子内鲜花数>=6时开始考虑倍增
// 若倍增后超过 井内鲜花数,则不倍增,否则倍增
// 若不倍增,看看对上次持有鲜花数倍增能否更接近答案,之后加一,重复这个过程;

int main()
{
    int t, l;
    cin >> t;
    while (t--)
    {
        scanf("%d", &l);
        int nf = 0;//当前篮子里鲜花数量
        int f = l;//当前井中鲜花数
        int lastf = 0;//上次记录井中鲜花数
        int coin = 0;//硬币数

        while (nf != l)
        {
            while (nf < 6 && f != 0) coin++, f--, nf++;
            while (f >= lastf&&nf!=l)
            {
                if (nf * 2 <= l && f >= nf) coin += 6, lastf = nf, nf += nf, f -= lastf;
                else {
                    while (f >= lastf && nf + lastf < l)coin += 2, nf += lastf, f -= lastf;
                }
            }
            while (nf != l) coin++, f--, nf++;
        }
        cout << coin << endl;
    }


    return 0;
}

这是简化后的dp

转自:鸣一YU

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;

int f[N];

void init()
{
    //f[i]表示i朵花的最少花费
    for(int i=1; i<=100000; i++)
    {

        //对于题目范围内的i,遍历其约数
        //其中，j 表示翻倍的倍数(2的个数)，即从 i/j 开始翻倍；i/j 表示翻倍后的数量，即每次翻倍的数量为 i/j；
        //i%(i/j) 表示最后一次翻倍时需要花费的额外费用(结尾补1)。

        //具体地，首先将 f[i] 更新为当前最小花费，然后枚举从 i/j 开始翻倍的倍数 j，计算翻倍后的数量
        //和最后一次翻倍的额外费用，然后加上 4+(j-1)*2，即投入 4 个硬币并记录新的数量的花费。最后，将
        //这个值与当前的 f[i] 取最小值，表示使用这种翻倍方式所需的最小花费。

        f[i]=i;//初始化i朵花最坏情况：每朵花都是一块钱买的
        for(int j=2; j<=i/j; j++)//j表示扩大的倍数
            f[i]=min(f[i], f[i/j]+4+(j-1)*2+i%(i/j));
            /*
              f[i/j]表示从i/j这个开始翻倍时的最小费用,
              f[i/j]+4+(j-1)*2+i%(i/j)这就是翻倍后的通用的推导公式；
            */
    }
}

int main()
{
    init();
    int t; cin >> t;
    for(int i=1; i<=t; i++)
    {
        int a ; cin >> a;
        printf("Case #%d: %d\n", i, f[a]);
    }
    return 0;
}