【题解】P6477 [NOI Online t2 提高组]子序列问题
t1炸了
注:本题解看似很长其实是非常详细,实则思路简单粗暴,容易理解
暴力优化
最暴力的做法即为枚举每一对 \(l\) , \(r\) ,并分别计算其 \(f(l,r)\) 的值。但这样不知道会慢到哪里去了,所以我们考虑只滚动 \(l\) 的值,并每次计算 \(G(l)=\sum_{r=l}^{n} f^2(l,r)\) 的值。
转移
考虑 \(G(l)\) 如何从 \(G(l-1)\) 转移过来,由 \(G\) 的定义:
\[\begin{aligned}
G(l-1)&=&f^2(l-1,l-1)+&f^2(l-1,l)&&+\cdots +f^2...