\(DP\)太菜了，开个随笔稍微记录一下
就……求出最长的，然后树上模拟？？
然后……数组忘了调大+\(sb\)错误\(WA\)了两发
这都能蓝？黄的差不多
问最长严格下降子序列长度，和数值不同的最长严格下降子序列个数
第一问\(O(n^2)dp\)，第二问我们发现，只要边\(dp\)边记录次数，然后往前更新答案的时候遇到同样的数字就\(break\)就行了
\(s[i][k]\)表示在\(i\)时刻\(k\)这个位置的前缀和，注意每个时刻机器人位置都变化所以这个前缀和是错位的……
然后就可以得到\(O(n^3)\)的\(dp\)方程：\(f[i]=max\{f[i-k]+s[i][j]-s[i-k][(j-k+p*n)\%n]-w[(j-k+p*n)\%n]\}\)
其中\(i\)是时间，\(j\)是当前位置，\(k\)是设定的移动距离
然后卡过了
为了有脸还是优化一下
然后我们变形一下方程得到 \(f[i]=max\{f[i-k]-s[i-k][(j-k+p*n)\%n]-w[(j-k+p*n)\%n]\}+s[i][j]\)
那单调队列维护一下前面这个\(max\)里的东西就好了
写起来稍微有点麻烦
先求出\(f[l][r]\)表示\([l,r]\)内能分出多少个单词，只要枚举\(r\)然后倒推\(l\)就可以\(O(n^2)\)实现
然后\(dp[i][k]\)表示到\(i\)分了\(k\)段的最大答案，注意\(k<=i\)
原文：https://www.cnblogs.com/knife-rose/p/12207415.html