【题解】NOI2009二叉查找树 + NOIP2003加分二叉树

　　自己的思维能力果然还是太不够……想到了这棵树所有的性质即中序遍历不变，却并没有想到怎样利用这一点。在想这道题的过程中走入了诸多的误区，在这里想记录一下 & 从中吸取到的教训（原该可以避免的吧）。

　　1. 注意到了中序遍历不变的性质却不会使用。

　　2. 注意到只有相对大小才会影响树的形态，在考虑的时候一直在想如何改变一个数的位置关系，分析修改权值对于树产生的影响。但这样是很难分析的，将树看作一个整体也不利于dp状态的划分。

　　3. 想不出怎样计算一个节点的深度（不能快速找到一个节点所处的位置）。

　　正确的思维应当是：

　　1.中序遍历不变 ---> 数值排名位于 [l, r] 这个区间中的所有树必然可能同在一棵子树中（且这棵子树中不含其他的节点）；

　　2.不好计算一个节点插入的深度 / 不好修改一个数在子树中的位置：改修改为插入。整棵子树中，唯一一个容易确定位置的节点：若这个节点是当前子树中权值最小的，则这个节点为子树的根，其余所有节点的深度 ++；

　　于是正确的 dp 状态就出来了。\(dp[l][r][v]\) 表示 \(l\) 到 \(r\) 的区间所有节点 \( >= v \) 的最小代价。转移方程分别为两种：修改该节点权值 & 不修改该节点权值。

　　　　\(dp[l][r][v] = dp[l][k - 1][v] + dp[k + 1][r][v] + K + sum[l][r];\)

　　　　\(dp[l][r][v] = dp[l][k - 1][P[i].v] + dp[k + 1][r][P[i].v] + sum[l][r];\)

　　其中，第二个转移方程中要求 \(P[i].v >= v\)，\(P[i].v\) 是节点原本的权值，\(sum[l][r]\) 为区间 \(l -> r\) 的访问频率。

#include <bits/stdc++.h>

using namespace std;

#define maxn 100

#define int long long

#define INF 999999999999LL

int n, K, sum[maxn];

int ans = INF, dp[maxn][maxn][maxn];

struct node

{

    int num, v, w;

}P[maxn];

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

bool cmp(node a, node b) { return a.v < b.v; }

bool cmp1(node a, node b) { return a.num < b.num; }

void gmin(int &x, int y) { x = x < y ? x : y; }

int dfs(int l, int r, int v)

{

    if(~dp[l][r][v]) return dp[l][r][v];

    else dp[l][r][v] = INF;

    if(l > r) return dp[l][r][v] = ;

    for(int k = l; k <= r; k ++)

    {

        gmin(dp[l][r][v], dfs(l, k - , v) + dfs(k + , r, v) + K + sum[r] - sum[l - ]);

        if(P[k].v >= v) gmin(dp[l][r][v], dfs(l, k - , P[k].v) + dfs(k + , r, P[k].v) + sum[r] - sum[l - ]);

    }

    return dp[l][r][v];

}

signed main()

{

    n = read(), K = read();

    memset(dp, -, sizeof(dp));

    for(int i = ; i <= n; i ++) P[i].num = read();

    for(int i = ; i <= n; i ++) P[i].v = read();

    for(int i = ; i <= n; i ++) P[i].w = read();

    sort(P + , P +  + n, cmp);

    for(int i = ; i <= n; i ++) P[i].v = i;

    sort(P + , P +  + n, cmp1);

    for(int i = ; i <= n; i ++) sum[i] += sum[i - ] + P[i].w;

    ans = min(ans, dfs(, n, ));

    printf("%lld\n", ans);

    return ;

}

　　2. 加分二叉树

　　双倍经验……

#include <bits/stdc++.h>

using namespace std;

#define maxn 40

#define int long long

int n, a[maxn];

int f[maxn][maxn], dp[maxn][maxn];

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

int dfs(int l, int r)

{

    if(dp[l][r]) return dp[l][r];

    if(l > r) return dp[l][r] = ;

    if(l == r) return  f[l][r] = l, dp[l][r] = a[l];

    for(int k = l; k <= r; k ++)

    {

        int x = dfs(l, k - ), y = dfs(k + , r);

        if(dp[l][r] < x * y + a[k])

        {

            dp[l][r] = x * y + a[k];

            f[l][r] = k;

        }

    }

    return dp[l][r];

}

void Get_ans(int l, int r)

{

    if(l > r) return;

    printf("%lld ", f[l][r]);

    Get_ans(l, f[l][r] - ), Get_ans(f[l][r] + , r);

}

signed main()

{

    n = read();

    for(int i = ; i <= n; i ++) a[i] = read();

    printf("%lld\n", dfs(, n));

    Get_ans(, n); puts("");

    return ;

}

巴特西

【题解】NOI2009二叉查找树 + NOIP2003加分二叉树

最新文章

热门文章