2021-2022 ICPC, NERC, Northern Eurasia Onsite J.Job Lookup（区间dp，二维前缀和)

链接 题意：给出一张完整的图片，给出两点之间的价值 c i j c_{ij} cij，现在你必须建造一棵二叉树。每个点的左儿子编号小于它，右儿子编号大于他。现在两点之间的权重是 d i j ? c i j d_{ij}*c_{ij} dij?cij， d i j d_{ij} dij为了树上的两点距离，现在你要让权值最小，谁是输出每一点的父节点？ n ≤ 200 n\le200 n≤2 0 0。 思路：首先假设我们已经构造出来了二叉树，我们的 w i j = c i j ∗ d i j w_{ij}=c_{ij}*d_{ij} wij​=cij​∗dij​，那么我们可以看成，把路径上的每一条边都加上一个 c i j c_{ij} cij​，这样一来，就成了一个前缀和。然后我们现在讨论如何构造树，如何求到权值，首先容易想到的就是区间dp，因为我们有限制，对于区间 [ l , r ] [l,r] [l,r]，枚举的k左子树范围是 [ l , k − 1 ] [l,k-1] [l,k−1]，右子树范围是 [ k + 1 , r ] [k+1,r] [k+1,r]，所以对于这个我们就可以跑区间dp，有了大概的转移 d p [ l ] [ r ] = d p [ l ] [ k − 1 ] + d p [ k + 1 ] [ r ] + n u m dp[l][r]=dp[l][k-1]+dp[k+1][r]+num dp[l][r]=dp[l][k−1]+dp[k+1][r]+num，现在我们的 k k k是根节点，我们有了左子树和右子树的和，现在还差左子树连向 k k k和右子树连向 k k k会产生的价值 n u m num num，根据我们之前讨论到的前缀和，所以我们左边子树会产生的价值就是矩阵 ∑ i ∈ [ l , k − 1 ] j ∈ [ 0 , l − 1 ] a i , j \sum_{i\in[l,k-1]}^{j\in[0,l-1]}a_{i,j} ∑i∈[l,k−1]j∈[0,l−1]​ai,j​和 ∑ i ∈ [ l , k − 1 ] j ∈ [ k , n − 1 ] a i , j \sum_{i\in[l,k-1]}^{j\in[k,n-1]} a_{i,j} ∑i∈[l,k−1]j∈[k,n−1]​ai,j​的和，右边子树同理，因为我们此时考虑的是走过这条边的点对所产生的权值，所以我们的 n u m num num就是这四个矩阵前缀和，最后记录一下路径就好，感觉这个反而是最简单的…记录路径这个。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[255][255], a[255][255], root[255][255], ans[255];
int dfs(int l, int r)
{ 
        
    int t = root[l][r];
    if (t - 1 >= l) ans[dfs(l, t - 1)] = t;
    if (t + 1 <= r) ans[dfs(t + 1, r)] = t;
    return t;
}

int calc(int x, int y, int xx, int yy)
{ 
        
    return a[xx][yy] - a[xx][y - 1] - a[x - 1][yy] + a[x - 1][y - 1];
}

signed main()
{ 
        
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) { 
        
        for (int j = 1; j <= n; j++) { 
        
            cin >> a[i][j];
            a[i][j] = a[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]; if(j >= i)dp[i][j] = 1e18;
        }
    }
    for (int len = 1; len <= n; len ++) { 
        
        for (int l = 1; l + len - 1 <= n; l++) { 
        
            int r = l + len - 1;
            for (int k = l; k <= r; k++) { 
        
                int d = dp[l][k - 1] + dp[k + 1][r] + calc(l, 1, k - 1, l - 1) + calc(l, k, k - 1, n) + calc(k + 1, 1, r, k) + calc(k + 1, r + 1, r, n);
                if (d < dp[l][r]) { 
        
                    root[l][r] = k;
                    dp[l][r] = d;
                }
            }
        }
    }
    dfs(1, n);
    for (int i = 1; i <= n; i++) { 
        cout << ans[i] << ' ' ;}
    return 0;
}