SHOI2017 分手是祝愿

未分类

原题链接：https://loj.ac/problem/2145

首先考虑给定一个$01$串，如何按照给定的规则把串全部变成$0$？
可以证明，在最优方案里每个位置最多被翻转一次，而且最优方案只有一个$(\{1,2\},\{2,1\})$算同一个.可以通过贪心的思路思考并证明：从大到小检查每个位置，如果当前位置是$1$，显然需要翻转，如果不翻转，将不存在任何方案能使该位置变成$0$；如果当前位置是$0$，显然不能翻转，如果翻转了，要使这位变回$1$，只能对这位再进行一次翻转，相当于没有翻转.以此类推，那么最优方案可以被唯一确定，时间复杂度是$O(nlogn)$.

由以上推论可以知道，和翻转次数期望有关的只有最优翻转次数.
设$dp(i)$为最优翻转次数为$i$的情况下翻转次数的期望.
显然当$0\leq i \leq k$时$dp(i)=i$.
当$k < i < n$时$dp(i)=\frac{(n-i)*dp(i+1)+i*dp(i-1)}{n}+1$
当$k=n$时,$dp(n)=dp(n-1)+1$.

当$k<i<n$时，可以把式子转换成$dp(i+1)=\frac{n*dp(i)-i*dp(i-1)-n}{n-i}$
需要用这个求解答案需要先求出$dp(k+1)$，问题就转换成了如何求解$dp(k+1)$.

设$dp(i)=a(i)*dp(k+1)+b(i),(k \leq i \leq n)$,$a(i),b(i)$不唯一.
显然$a(k)=0,b(k)=k,a(k+1)=1,b(k+1)=0;$
通过$dp(i+1)=\frac{n*dp(i)-i*dp(i-1)-n}{n-i}$可以求出$a^1(n),b^1(n)$
通过$dp(n)=dp(n-1)+1$可以求出$a^2(n),b^2(n)$.
那么可以知道$dp(k+1)=\frac{b^2(n)-b^1(n)}{a^1(n)-a^2(n)}$.

设$cnt$为初始序列的最优翻转次数.
注意特判$k \ge cnt$或$k\ge n-1$时答案为$cnt$.

最后答案乘上$n!$.