NOI 2009 二叉查找树

This post is written in Chinese. Please consider using Google Translate

问题简述

有一棵Treap，每个节点有一个互不相同的数据值和权值，以及一个访问频度。一个节点的访问代价为它的访问频度乘以它在树中的深度，整棵树的访问代价定义为所有节点的访问代价之和。节点的权值可以修改为任意实数，每修改一个节点的权值的代价为K。任务是修改一些节点的权值，使得整棵树的访问代价与修改代价之和最小。

问题建模

首先离散化所有节点的权值，对所有节点按照数据值排序后线性存储。定义S[i,j]为(排序后)第i个节点到第j个节点的访问频度之和。

解法 动态规划

算法描述
定义Weight[i]为状态转移方程为第i个节点离散化后的权值，F[i,j,w]表示从第i个节点到第j个节点组成一棵子树的最小代价，子树根节点的权值≥w。状态转移方程为

clip_image002

边界条件为clip_image004，目标函数为clip_image006。

算法分析
对于一个状态F[i,j,w]，我们要枚举从节点[i..j]组成的这棵子树的根节点k，其左子树为[i..k-1]，右子树为[k+1..j]。

如果根节点k的权值Weight[k]≥w，那么节点k的权值无需修改即可直接作为该子树的根节点。总代价为左子树的代价F[i,k-1, Weight[k]]，加上右子树的代价F[k+1,j, Weight[k]]，以及整个子树的访问频度之和。

另外一种情况，修改节点k的权值，使之不小于w。由于我们已经离散化了权值，修改后的权值不应是整数，以免和已有重复。假设节点k修改后的权值为w加上一个很小的小数，其左右子树根节点的权值都不应小于节点k修改后的权值。我们约定如果根和子节点都必须大于w的话，则子节点的权值比根节点略大，且大于w。于是这种情况的总代价为左子树的代价F[i,k-1, w]，加上右子树的代价F[k+1,j, w]，加上修改权值的代价K，以及整个子树的访问频度之和。

复杂度分析
状态数为O(N3)，每次转移需要以O(N)的时间枚举k，所以时间复杂度为O(N4)。在实际测试中通过了所以测试点，得到100分。

参考程序

/* 
 * Problem: NOI2009 treapmod
 * Author: Guo Jiabao
 * Time: 2009.9.24 14:50
 * State: Solved
 * Memo: 动态规划
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;

typedef long long big;

const int MAXN = 72;
const big INF = ~0ULL>>1;

struct node
{
    int val,wei,freq;
}P[MAXN];

int N,K;
big sf[MAXN],F[MAXN][MAXN][MAXN],Ans=INF;

void init()
{
    int i;
    freopen("treapmod.in","r",stdin);
    freopen("treapmod.out","w",stdout);
    scanf("%d%d",&N,&K);
    for (i=1;i<=N;i++)
        scanf("%d",&P[i].val);
    for (i=1;i<=N;i++)
        scanf("%d",&P[i].wei);
    for (i=1;i<=N;i++)
        scanf("%d",&P[i].freq);
    memset(F,-1,sizeof(F));
}

inline int cmp1(const void *a,const void *b)
{
    return ((node *)a) -> wei - ((node *)b) -> wei;
}

inline int cmp2(const void *a,const void *b)
{
    return ((node *)a) -> val - ((node *)b) -> val;
}

inline big sum(int i,int j)
{
    return sf[j] - sf[i-1];
}

big dp(int i,int j,int w)
{
    if (i>j)
        return 0;
    if (F[i][j][w] == -1)
    {
        int a;
        big t,rs=INF;
        for (a=i;a<=j;a++)
        {
            t = dp(i,a-1,w) + dp(a+1,j,w) + sum(i,j) + K;
            if (t < rs)
                rs = t;
            if (P[a].wei >= w)
            {
                t = dp(i,a-1,P[a].wei) + dp(a+1,j,P[a].wei) + sum(i,j);
                if (t < rs)
                    rs = t;
            }
        }
        F[i][j][w] = rs;
    }
    return F[i][j][w];
}

void solve()
{
    int i;
    qsort(P+1,N,sizeof(P[0]),cmp1);
    for (i=1;i<=N;i++)
        P[i].wei = i;
    qsort(P+1,N,sizeof(P[0]),cmp2);
    for (i=1;i<=N;i++)
    {
        P[i].val = i;
        sf[i] = sf[i-1] + P[i].freq;
    }
    for (i=0;i<=1;i++)
    {
        big t = dp(1,N,i);
        if (t < Ans)
            Ans = t;
    }
}

int main()
{
    init();
    solve();
    cout << Ans << endl;
    return 0;
}

Related posts