加深了对树形区间 dp 的理解。

设 $f_{l,r}$ 表示把区间 $[l,r]$ 中的所有点拿出来建出一颗 DFS 树，且这棵 DFS 树其中 $l$ 是根的最小代价。这样设计状态保证了遍历完一棵子树之后的回溯的点是确定的。

然后考虑转移，现在合并区间 $[l,k],[k+1,r]$ 相当于合并两个子树，然后把第二个子树拼到第一个子树的根。

这样有一种转移 $f_{i,j}=\min\limits_{k=i}^j \{ f_{i,k}+f_{k+1,j}+\max\{0,a_{i,k+1}\}\}$。对 $0$ 取 $\max$ 的目的是，如果这条边已经存在，那么不需要手动添加这条边代价是 $0$。

但是这个转移是不对的，需要考虑 $f_{i,k}$ 和 $f_{k+1,j}$ 中已经存在的横叉边，这就比较麻烦。

重新考虑状态，设 $f_{l,r}$ 表示把区间 $[l,r]$ 中的所有点拿出来建出一颗 DFS 树，这棵 DFS 树其中 $l$ 是根，且不存在向大于 $r$ 的点的横叉边的最小代价。

这个时候转移只需要多一步，在按照以上的式子转移好后，对于 $f_{i,j}$ 还需要加上 $\sum\limits_{k=j+1}^n \max\{0,-a_{i,k}\}$ 的代价，代表去除已经存在的往后连的横叉边。

时间复杂度 $O(n^3)$。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr ll N=755;
ll n,a[N][N],dp[N][N],sum[N][N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    memset(dp,0x3f,sizeof(dp));
    for(int j=2;j<=n;j++){
        for(int i=1;i<j;i++){
            cin>>a[i][j];
            //a[j][i]=a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        a[i][i]=0;
        for(int j=n;j>i;j--){
            sum[i][j]=sum[i][j+1]+max(0ll,-a[i][j]);
        }
    }
    for(int i=n;i>=1;i--){
        dp[i][i]=0;
        for(int j=i+1;j<=n;j++){
            for(int k=i;k<=j;k++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+max(0ll,a[i][k+1]));
            }
        }
        for(int j=i;j<=n;j++){
            dp[i][j]+=sum[i][j+1];
        }
    }
    cout<<dp[1][n]<<"\n";
    return 0;
}