这道题我在做的时候只差一个引理就做出来了。
如果k=n，则可以贪心。从大到小按开关即可。
这样子可以拿到50（实测80）分。
实际上，如果枚举约数写挂了（枚举j*j<=n而不是i）也能得到55分。
如果k!=n，则需要用到另一个结论：如果当前局面随便按一个点，顺序是正确的，则最优次数会-1，否则会+1
如果知道了这个结论，那么我们可以设计一个dp。
题目在终止的次数<=k时直接使用最优决策。
设f[i]表示从i按到i-1用的期望步数。
$f[i]=frac{i}{n}+frac{n-i}{n}*(f[i]+f[i+1]+1)$
它的意思是：有i/n的概率可以按到正确的开关，有(n-i)/n的概率为错误的位置。
此时我们需要从i+1按到i，再按一次，再按到i-1
化式子得到$f[i]=frac{n+(n-i)*f[i+1]}{i}$
我们要从现在最优方案c按到k+1，则把这些f全部累加起来。