Pay to win – 题解

Pay to win – 题解

当年陈刀仔只用20块能赢到三千七百万,我今天用A,B,C,D赢到N,不是问题。

问题描述

你现在手里只有数字0,但你有非常多的筹码。

  • 花费A枚筹码将手中的数字变为2倍
  • 花费B枚筹码将手中的数字变为3倍
  • 花费C枚筹码将手中的数字变为5倍
  • 花费D枚筹码将手中的数字增加1或者减少1.

你的筹码非常多,但是还是要省着用。这一场给定一个数字N,试计算要将手中的0变为数字N,最少消耗几枚筹码。

分析

我们可以把这个问题反过来想:手中初始是数字N最终变为0。可以采取以下的操作:

  • 如果\( x \)能被2整除,则用\(\frac{x}{2}\)替代\(x\) 并花费A枚筹码
  • 如果\( x \)能被3整除,则用\(\frac{x}{3} \)替代\(x\) 并花费B枚筹码
  • 如果\( x \)能被5整除,则用\(\frac{x}{5} \)替代\(x\) 并花费C枚筹码
  • 用\(x+1\) 或\(x-1\)替代\(x\) ,花费D枚筹码

一种方法是,我们全用花费D的方法,这样从N到0的花费为\(ND\).另外,我们可以采用这样的策略:
\[ N \stackrel{D}{\longmapsto}…\stackrel{D}{\longmapsto}ky \stackrel{k}{\longmapsto} y\]
其中\( k \in \{2,3,5\}\).当然要保证 \( y \in \{ \lfloor \frac{N}{k} \rfloor, \lceil \frac{N}{k} \rceil\}\).

事实上,如果 \(y<\lfloor \frac{N}{k} \rfloor\)(同样的理由对\(y>\lceil \frac{N}{k} \rceil \)也适用),就有如下的变换序列,比上述序列的花费更低
\[ N \stackrel{D}{\longmapsto}…\stackrel{D}{\longmapsto} k\lfloor \frac{N}{k} \rfloor \stackrel{k}{\longmapsto} \lfloor \frac{N}{k} \rfloor \stackrel{D}{\longmapsto}… \stackrel{k}{\longmapsto} y\]

所以,我们的最优策略是直接用(\pm1)的方式由N到0,或到某个
\( { \lfloor \frac{N}{k} \rfloor, \lceil \frac{N}{k} \rceil})
((k \in {2,3,5})\)。
特别地,如果记\( f(n) \)为从\(N\)到0的最小花费,那么如果我们知道了\(f( \lfloor \frac{N}{k} \rfloor)\)和\( f( \lceil \frac{N}{k} \rceil)\),那么\(f(n)\)便可容易计算出。

上述讨论可以用动态规划方法实现,但是还需要解决从N到0有多少状态的问题。可以证明,可达的数字将由以下两式限定
\[ \lfloor \frac{N}{2^a3^b5^c} \rfloor , \lceil \frac{N}{2^a3^b5^c} \rceil \]

由于\( 0 \leq a \leq 60, 0 \leq b \leq 40 , 0 \leq c \leq 30 \)
\(不然分母将大于分子\),可达的数字小于\(2\times 61 \times 41 \times 31= 155062\)
(为了Accepted,程序要保证(f(n))总是在n的可达数字以内)

发表评论

电子邮件地址不会被公开。 必填项已用*标注