模板

洛谷 P1063

for(int len=2;len<=n;len++) 
        for(int i=1;i+len-1<=2*n;i++){
            for(int k=i;k<=i+len-2;k++){
                // k 为分段点
                dp[i][i+len-1]=max(dp[i][i+len-1],dp[i][k]+dp[k+1][i+len-1]+a[i]*a[k+1]*a[i+len]);
            }
        }

其实学过多重背包之后就很好理解了qwq
因为是两个两个合并的，所以从宏观来说就是从小的几个到大的几个合并过程
有人可能要问了，为什么明明题目是两个两个合并，但你这里却不考虑？
因为合并之后原信息仍然可以通过初始信息算出
例如这道题，假设三个球头尾标记分别是 2,3,4,5，把后两个合并起来后是 2,3,5 还是能从原信息中算出的，如果把题目改成 a,b,c 合并后 a*b,b*c，那就不能用做了至少我不会，有大佬会可以指出来
区间 dp 还有一个隐含条件是合并次数，一般会给出合并后最后物品的数量，或者直接给出

一些思考(11.21加)

今天在做 P4302 的时候卡住了，一开始想的很复杂，主要还是因为状态转移的问题。一开始我觉得为了减少复杂度，应该从下面把相关信息传递上来。
但其实我还是没能读懂区间dp的本质，就是原信息仍然可以通过原信息算出
那么在做这道题的时候，求能不能折叠，也应该由原信息推出，而不是通过状态转移
虽然也许可以
但是说回来dp这种东西本身复杂度就很高，其实本质上这种题还是通过枚举来做的，只不过dp解决的是怎么样不重不漏地完成枚举

两些思考(11.23加)

昨天做 P1220 的时候又卡住了，主要一直在想断点的问题，但这道题很巧的一点是关完一个区间的灯之后一定是站在端点的。然后这样的话，断点就为 l+1 或 r-1，就没有枚举的必要了。

三些思考(11.26加)

今天做P3592没做出来，去看了题解，还是状态转移难想