题解：P11676 [USACO25JAN] DFS Order P

· · 题解

加深了对树形区间 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;
}