题意

一个$N$个面的骰子，开始的值是$S$，现在希望到$T$，你可以做两种操作，操作可以任意顺序，任意次：

1.花费$A$：将$S$加$1$，但要注意$S$等于$N$时不可以进行该操作。

2.花费$B$：随机投掷骰子一次，等概率出现$1-N$之间的数。

寻求一种$S$到$T$期望花费最小的策略，输出最小期望。

范围

思路

​ 首先思考，如果一个骰子做了操作1在做操作2，这是十分奇怪的，因为既然要做操作2，何必做操作1呢，先做的操作1不会对操作2有任何影响。因此得出第一个结论：先做操作2，再做操作1(也可以不做操作2直接做操作1,总之不能做完操作1再做操作2)。

​ 那么掷到多大才可以做操作1呢？不妨设为$X$, 那么投掷到目标区间$[T-X+1,T]$的时候就可以直接进行操作1，直到T，要么就一直进行操作2。因此期望就是: 投掷到目标区间花费的期望$E_1$+从目标区间到T的期望$E_2$。

​ 首先考虑$E_2=(X-1)*A/2$，这个计算就是一个线性期望计算。

​ 然后重点考虑$E_2$的计算，设第$i$次才投到目标区间的概率为$p_i$, 则:

$$E_2=\Sigma_{i=1}^{\inf}p_i*i*B$$

然后就是高中数列知识错位相减得到结果即可，答案是$BN/2$。

所以期望就是: $BN/2 + (X-1)A/2$，利用均值不等式:$BN/2 + (X-1)A/2>=\sqrt{ABN/2}-N/2$即可。