区间 DP

[Ir1d]

https://oi-wiki.org/dp/interval/

[eqvpkbz]

团队题目蜈蚣无权限访问还行

[Ir1d]

@eqvpkbz 谢谢提醒！

[AutumnDustPappet]

代码中应该是k < j吧，而不是k <= j

[see3p00]

核心代码第4行应该是 k<j

[Transmigration-zhou]

len为什么不是从2枚举

[guandy-daydayup]

len应该从2开始枚举吧

[yaoyunzhou]

最小值求法类似：

g[i][j] = std::min(g[i][j], g[i][k] + g[k + 1][j] + sum[j] - sum[i - 1]);

[Mys-Ept]

注：求最小值时，每次求dp[i][j]时，要先将dp[i][j]赋到极大值，然后再for(int k=i;i<j;++k)让dp[i][k]变小。
否则一直是0。

[ursulalujun]

核心代码好像有点问题，只限制了k的范围，没限制j的范围，j会越界，给出我的AC代码（java），我是限制了i的范围，这样能保证算出的j不会越界。

// 遍历每种区间长度
for (int len = 2; len <= n; len++) {
    // 遍历每个区间的起始位置
    for (int i = 1; i <= 2 * n + 1 - len; i++) {
        int j = i + len - 1; // 区间的终止位置
        // 遍历区间内的每个位置，找到最大得分和最小得分
        for (int k = i; k < j; k++) {
            max[i][j] = Math.max(max[i][j], max[i][k] + max[k + 1][j] + sum[j]-sum[i-1]);
        }
    }
}

还有处理环的第二种方法，我不明白为什么f(n,2n-1), f(n+1,2n)这两个不用参与比较？

[Mys-Ept]

f(n,2n-1)是参与了比较的。但是(n+1, 2n)和(1, n)是完全一样的，所以可以省略掉 f(n+1, 2n)。
也就是说循环条件是i<=2n-len ，最后一个格子不遍历。
实际上写成i<=2n-len+1也没什么区别，答案不变，也不差这一点时间损失

[hanwenlaohu]

为啥f(n,2n-1)没有被拿出来比较啊，感觉不太对啊，有没有大佬出来说一下啊

[Chlero]

改了

[firewolf144]

i <= 2 * n - 1 - len 为什么要-1啊

[Chlero]

改了

[Mys-Ept]

最小值和最大值求法相似，只需将记得每次求的时候先赋值成极大值，不然min()的结果会一直是0
dp1 最小值 dp2最大值

    for(int len=2;len<=n;++len){
        for(int j,i=1;i<=2*n-len+1;++i){  //最后一个位置与第一个位置重复了,可以是i<=2*n-len
            j=i+len-1;
            dp1[i][j]=0x7fffffff;
            for(int k=i+1;k<=j;++k){
                dp1[i][j]=min(dp1[i][j],dp1[i][k-1]+dp1[k][j]+sm[j]-sm[i-1]);
                dp2[i][j]=max(dp2[i][j],dp2[i][k-1]+dp2[k][j]+sm[j]-sm[i-1]);
            }
        }
    }