关于树形 DP
  • 板块学术版
  • 楼主LCat90
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/11/15 19:16
  • 上次更新2023/11/15 20:40:30
查看原帖
关于树形 DP
487539
LCat90楼主2023/11/15 19:16

要使时间为 O(n2)O(n^2),下面的第二层循环应该正序枚举吗?

for(auto to : G[x]) {
        if(to == fa) continue ;
        dfs(to, x);
        for(int i = siz[x];i >= 0; --i)
            for(int j = siz[to];j >= 1; --j) {
                  if(i) dp[x][i + j][1] = min(dp[x][i + j][1], dp[x][i][1] + min(dp[to][j][0], dp[to][j][1]));
                  dp[x][i + j][0] = min(dp[x][i + j][0], dp[x][i][0] + dp[to][j][0]);
            }
        siz[x] += siz[to];
2023/11/15 19:16
加载中...