题解 P5241 【序列】

· · 题解

这是一道原题的加强版

考虑这么一个事情：给定一个序列，判断是否能得到

那么就是一开始先不断加边形成一条链，每次强连通分量数量如果变化，就缩链上开头的一部分（这一部分一定要弱联通）

当弱联通之后（就是所有点都被串到链上之后）就可以“为所欲为”了，只要边的数量不超过当前强连通分量数下能达到的边数最大值即可，边数最大值就是把链上开头一段缩起来得到的

这是一个贪心的过程

可以发现明显分成了两个过程

对于两个过程分别dp

第一个过程的dp，设F[n][cnt][x]表示当前链上的前n个点是联通的，强连通分量变化了cnt次，链上的前x个点被缩了起来。这时候边的数量是n−1+cnt条

第二个过程的dp，设G[m][x]表示当前的边数为m，链上的前x个点被缩了起来的方案数。需要满足m≤C(N,2)+C(x,2)

这两个dp显然都可以直接前缀和优化做到O(1)转移

状态都是O(N^3)的，所以时间复杂度也是O(N^3)的