专栏文章

题解：P11676 [USACO25JAN] DFS Order P

rreinforest
P11676题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minn5cfe
此快照首次捕获于
2025/12/02 05:08
3 个月前
此快照最后确认于
2025/12/02 05:08
3 个月前
查看原文
加深了对树形区间 dp 的理解。
设 fl,rf_{l,r} 表示把区间 [l,r][l,r] 中的所有点拿出来建出一颗 DFS 树，且这棵 DFS 树其中 ll 是根的最小代价。这样设计状态保证了遍历完一棵子树之后的回溯的点是确定的。
然后考虑转移，现在合并区间 [l,k],[k+1,r][l,k],[k+1,r] 相当于合并两个子树，然后把第二个子树拼到第一个子树的根。
这样有一种转移 fi,j=min⁡k=ij{fi,k+fk+1,j+max⁡{0,ai,k+1}}f_{i,j}=\min\limits_{k=i}^j \{ f_{i,k}+f_{k+1,j}+\max\{0,a_{i,k+1}\}\}。对 00 取 max⁡\max 的目的是，如果这条边已经存在，那么不需要手动添加这条边代价是 00。
但是这个转移是不对的，需要考虑 fi,kf_{i,k} 和 fk+1,jf_{k+1,j} 中已经存在的横叉边，这就比较麻烦。
重新考虑状态，设 fl,rf_{l,r} 表示把区间 [l,r][l,r] 中的所有点拿出来建出一颗 DFS 树，这棵 DFS 树其中 ll 是根，且不存在向大于 rr 的点的横叉边的最小代价。
这个时候转移只需要多一步，在按照以上的式子转移好后，对于 fi,jf_{i,j} 还需要加上 ∑k=j+1nmax⁡{0,−ai,k}\sum\limits_{k=j+1}^n \max\{0,-a_{i,k}\} 的代价，代表去除已经存在的往后连的横叉边。
时间复杂度 O(n3)O(n^3)。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...