LibreOJ-3614Luogu-P9040很好的题。先不考虑区间，先想\(l=1,r=n\)的情况。考虑dp，\(f_i\)表示考虑\([l,r]\)的答案。则容易得到：\[f_i=\max\left\{f_{i-1},f_{i-k}+s_i-s_{i-k}\right\},f_0=0\]其中\(s\)为\(a\)的前缀和。这个转移本身是\(\Theta(n)\)的。遇

[PA2019]DesantSolution原题链接。题目大意：给定一个长为\(n(n\le40)\)的排列，对于每个\(i\)求出长度为\(i\)的子序列逆序对最少有多少，并且求出有多少个长度为\(i\)的子序列逆序对最少。解题思路：首先有一个暴力的做法，设\(f_{i,S}\)表示考虑完前\(i\)个数，选择了集