【SHOI2017】分手是祝愿题解(dp毒瘤)

oisdoaiu · 2020-05-06 16:03:40 · 题解

50分部分分入手

其实有80分

首先考虑k=n的部分分

• 倒着扫，遇到有1的位置就操作一下

正确性：

• 一个点不会被操作2次以上，因为2次操作相当于没操作

• 操作i不会影响到比i大的数

• 所以从后往前扫，若遇到1不操作，那么前面的操作也不会改变这个1，所以必须操作

正解

首先若最小步数小于等于k，直接输出ans\cdot n!就好了

问题在于最小步数大于k的情况

容易发现上面那个操作序列是固定的

用一个01序列表示每个点需不需要操作（例子：101100表示1,3,4需要被操作）

然后容易发现最优的操作次数即为这个序列中1的个数，也就是说和序列长什么样子无关，只关心有多少个1

所以考虑设f[i]表示序列中有i个1的期望操作次数

• 如果乱选选到了0，1的个数会多一个
• 如果乱选选到了1，1的个数会少一个
• 所以有：f[i]=\frac inf[i-1]+\frac{n-i}nf[i+1]+1

然后是玄学推式子

• 注意到f[n]=f[n-1]+1，我们把它作为边界条件
• f[n-1]=\frac{n-1}n f[n-2]+\frac1n f[n]+1
• 将第一个式子带入
• f[n-1]=\frac{n-1}n f[n-2]+\frac1n f[n-1]+\frac{n+1}n
• 移项后处理一下系数得到：
• f[n-1]=f[n-2]+\frac{n+1}{n-1}

发现这个东西长成这个样子f[n]=f[n-1]+常数，f[n-1]=f[n-2]+常数

然后大胆猜想不需要求证，加的这个常数(设为g[i])可以递推出来

• f[i-1]=\frac{i-1}n f[i-2]+\frac{n-i+1}n f[i]+1
• 因为我们猜想f[i]=f[i-1]+g[i]，将它带入
• f[i-1]=\frac{i-1}n f[i-2]+\frac{n-i+1}n f[i-1]+\frac{n-i+1}ng[i]+1
• 移项后处理一下系数：
• f[i-1]=f[i-2]+\frac{n-i+1}{i-1}g[i]+\frac n{i-1}
• 所以有：g[i-1]=\frac{(n-i+1)g[i]+n}{i-1}
• 换个样子：g[i]=\frac{(n-i)g[i+1]+n}i

然后g[i]就可以倒着递推出来了

接着f[i]也可以正着递推出来

dp式子总结

• f[k]=k
• f[i]=f[i-1]+g[i]
• g[n]=1
• g[i]=\frac{(n-i)g[i+1]+n}i