NOI2013 二叉查找树

题目链接:戳我

对于一个排序二叉树来讲,它的中序遍历对应的序列是可以确定的.

我们知道如果求一个访问频率最低的(也就是没有修改),直接就区间DP即可.\(dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1])\)(其中sum表示访问频率的前缀和)

但是现在带上了修改qwq,所以我们肯定要多出来一个键值相关的维度.

键值很大,但是它的具体大小没什么意义,我们只需要知道他们的相对大小就行了,所以先离散化一下.我们可以凭借一个区间的最小的键值,来确定该区间表示的子树的根.

所以现在令\(f[i][j][k]\)表示在[i,j]区间中,最小的键值为k的答案.

那么有转移方程:

\(f[i][j][k]=min(f[i][p-1][k]+f[p+1][j][k]+sum[j]-sum[i-1]+K)\)(表示把p改为k)

\(f[i][j][k]=min(f[i][p-1][t[p].key]+f[p+1][j][t[p].key]+sum[j]-sum[i-1])\)(表示不对p进行修改)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define MAXN 75

using namespace std;

int n,K,tot,ans;

int sum[MAXN],pre[MAXN],f[MAXN][MAXN][MAXN];

struct Node{int key,s,id;}node[MAXN];

inline bool cmp(struct Node x,struct Node y){return x.id<y.id;}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("ce.in","r",stdin);

    #endif

    scanf("%d%d",&n,&K);

    for(int i=1;i<=n;i++) scanf("%d",&node[i].id);

    for(int i=1;i<=n;i++) scanf("%d",&node[i].key),pre[++tot]=node[i].key;

    for(int i=1;i<=n;i++) scanf("%d",&node[i].s);

    sort(&node[1],&node[n+1],cmp);

    sort(&pre[1],&pre[tot+1]);

    tot=unique(&pre[1],&pre[n+1])-pre-1;

    for(int i=1;i<=n;i++) node[i].key=lower_bound(&pre[1],&pre[tot+1],node[i].key)-pre;

    memset(f,0x3f,sizeof(f));

    for(int i=1;i<=n+1;i++)

        for(int k=1;k<=n;k++)

            f[i][i-1][k]=0;

    for(int i=1;i<=n;i++)

        for(int k=1;k<=n;k++)

        {

            f[i][i][k]=node[i].s;

            if(node[i].key<k) f[i][i][k]+=K;

        }

    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+node[i].s;

//	for(int i=1;i<=n;i++) printf("sum[%d]=%d\n",i,sum[i]); puts("");

    for(int k=n;k>=1;k--)

    {

        for(int len=1;len<=n;len++)

        {

            for(int i=1,j=i+len-1;i<=n&&j<=n;i++,j++)

            {

                for(int p=i;p<=j;p++)

                {

                    int cur=node[p].key;

                    f[i][j][k]=min(f[i][j][k],f[i][p-1][k]+f[p+1][j][k]+sum[j]-sum[i-1]+K);

                    if(cur>=k)

                        f[i][j][k]=min(f[i][j][k],f[i][p-1][cur]+f[p+1][j][cur]+sum[j]-sum[i-1]);

                }

            }

        }

    }

    printf("%d\n",f[1][n][1]);

    return 0;

}

巴特西

NOI2013 二叉查找树

题目链接:戳我

最新文章

热门文章