\(O(n^3)\) 的朴素 \(dp\) 是 simple 的
考虑定义一个子序列是”好的子序列”当且仅当 \(a_l\) 和 \(a_r\) 都在子序列中，容易发现他对答案的贡献是包含他的区间，即 \(l \times (n - r + 1)\)
先说我自己的做法：设 \(dp_{i,j}\) 表示强制以 \(i\) 结尾，子序列和为 \(j\) 的答案，注意这里要带上他的左端点系数，即 \(l\)
容易得到递推式：
\[\begin{cases} dp_{i,j} = \sum_{j<i} dp_{i,j-a_i} & (j > a_i) \\ dp_{i,j} = i & (j = a_i) \end{cases} \]其中可以用前缀和优化转移，做到 \(O(n^2)\)
题解里做法大同小异，他们但去掉了强制的设定，变成了一个 01 背包问题然后求解，而对于钦定
最终复杂度 \(O(n^2)\)
标签：ABC159F,Segments,Knapsack,序列,cases,dp From： https://www.cnblogs.com/fox-konata/p/17766611.html