NOI2009 二叉查找树

题目:

  已知一棵特殊的二叉查找树。根据定义,该二叉查找树中每个结点的数据值都比它左儿子结点的数据值大,而比它右儿子结点的数据值小。
  另一方面,这棵查找树中每个结点都有一个权值,每个结点的权值都比它的儿子结点的权值要小。
  已知树中所有结点的数据值各不相同;所有结点的权值也各不相同。这时可得出这样一个有趣的结论:如果能够确定树中每个结点的数据值和权值,那么树的形态便可以唯一确定。因为这样的一棵树可以看成是按照权值从小到大顺序插入结点所得到的、按照数据值排序的二叉查找树。
  一个结点在树中的深度定义为它到树根的距离加 。因此树的根结点的深度为
  每个结点除了数据值和权值以外,还有一个访问频度。我们定义一个结点在树中的访问代价为它的访问频度乘以它在树中的深度。整棵树的访问代价定义为所有结点在树中的访问代价之和。
  现在给定每个结点的数据值、权值和访问频度,你可以根据需要修改某些结点的权值,但每次修改你会付出 $K$ 的额外修改代价。
  你可以把结点的权值改为任何实数,但是修改后所有结点的权值必须仍保持互不相同。现在你要解决的问题是,整棵树的访问代价与额外修改代价的和最小是多少?

思路:

  首先深度 权值的代价可以转化成每个点子树的权值和。
  既然是子树就能用 dfs 序转化成区间了,每次枚举一个点做根。但是这样就出现了一个问题:这个根是变小成为根,还是把其他数字变大成为根?
  所以在 dp 状态中再加一维,设 表示 内最后权值都大于 的最小代价。
  转移也就比较显然了,讨论当前枚举到的根权值是否大于 即可。(具体看代码)

代码:

#include <bits/stdc++.h>
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 75;

int n, k, val[N], id[N], hvy[N], cnt[N], vec[N];
int dp[N][N][N];

int dfs(int l, int r, int w) {
    if(l > r) return 0;
    int &ans = dp[l][r][w];
    if(ans != -1) return ans;
    ans = 1e9;
    int s = 0;
    rep(x, l, r) {
        int o = id[x];
        s += cnt[o];
        if(hvy[o] > w) tomin(ans, dfs(l, x - 1, hvy[o]) + dfs(x + 1, r, hvy[o]));
        tomin(ans, dfs(l, x - 1, w) + dfs(x + 1, r, w) + k);
    }
    return ans += s;
}

bool cmp(int a, int b) {
    return val[a] < val[b];
}

int main() {
    File(treapmod);
    scanf("%d%d", &n, &k);
    int tot = 0;
    rep(i, 1, n) scanf("%d", val + i);
    rep(i, 1, n) scanf("%d", hvy + i), vec[++tot] = hvy[i];
    rep(i, 1, n) scanf("%d", cnt + i);
    sort(vec + 1, vec + 1 + tot);
    rep(i, 1, n) hvy[i] = lower_bound(vec + 1, vec + 1 + tot, hvy[i]) - vec;
    rep(i, 1, n) id[i] = i;
    sort(id + 1, id + 1 + n, cmp);
    mset(dp, -1);
    int ans = 1e9;
    rep(i, 0, tot) tomin(ans, dfs(1, n, i));
    printf("%d\n", ans);
    return 0;
}