「BZOJ4361」ISN-树状数组+DP

发布于 2018-10-03  115 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「BZOJ4361」ISN-树状数组+DP

Description

给出一个长度为\(n\)的序列\(A(A_1,A_2...A_n)\)。如果序列\(A\)不是非降的,你必须从中删去一个数,
这一操作,直到\(A\)非降为止。求有多少种不同的操作方案,答案模\(10^9+7\)。

\(n \leqslant 2000\)

Solution

设\(f_i\)表示长度为\(i\)的不降序列数,这个可以用树状数组\(O(n^2logn)\)求。

把答案按最后剩下的长度分类,\(ans=\sum_{i=1}^n f_i \times (n-i)!\)

由于当序列非降时会停止,所以会有一部分算重。

考虑每种长度为\(i\)的不合法情况是由一种长度为\(i+1\)的序列删去一个数得到,所以答案减去\(f_{i+1}\times (i+1) \times (n-i-1)!\)

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「BZOJ4361」ISN-树状数组+DP


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前, 相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!