[NOI2009]二叉查找树

DP

---

题面

戳我

解析

我刚看到这道题时无从下手，连$DP$状态都不知道怎么设。。。
于是坠入题解的深渊

根据定义，该二叉查找树中每个结点的数据值都比它左儿子结点的数据值大，而比它右儿子结点的数据值小。
则因数据值不会被修改，所以树的中序遍历不变（先左再中后右）。
于是我们可以在树的中序遍历上进行区间$DP$，一个区间就能代表一颗子树。

又因为是否加上$k$代价取决于子树根结点与其祖先结点的关系（权值不能比祖先小，否则你把哪个点当整个树的根都可以），我们应该在状态中维护该子树根节点的值。即状态为$f[l][r][w]$表示在$l$到$r$区间内，根节点权值为$w$的子树的访问代价。

于是就可以列转移方程式：($s[i]$是访问频率前缀和）

$$if(a[i].w>=w)\\ f[l][r][w]=min(ans,f[l][i-1][a[i].w]+f[i+1][r][a[i].w]+s[r]-s[l-1])$$
$$f[l][r][w]=min(ans,f[l][i-1][w]+f[i+1][r][w]+s[r]-s[l-1]+k)$$

又注意到$w$数据范围似乎很大（$4*10^5$),由于权值只要比较相对大小就可以了，直接离散化（然后我的离散化因为一开始不排序而gg！！！详见代码注释部分）。
我选择了写着更舒服的记搜。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
struct node{ll dat,w,v;bool operator < (const node &o) const{return dat<o.dat;}}a[100];
struct pzy{ll w,id;bool operator < (const pzy &o) const{return w<o.w;}}b[100];
ll n,k,o[100],s[100],len,dp[100][100][100];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il ll dfs(re int l,re int r,re int w)
{
    re ll ans=2e9;
    if(dp[l][r][w]!=-1) return dp[l][r][w];
    if(l>r) return dp[l][r][w]=0;
    fp(i,l,r)
    {
        if(a[i].w>=w) ans=min(ans,dfs(l,i-1,a[i].w)+dfs(i+1,r,a[i].w)+s[r]-s[l-1]);
        ans=min(ans,dfs(l,i-1,w)+dfs(i+1,r,w)+s[r]-s[l-1]+k);
    }
    return dp[l][r][w]=ans;
}
int main()
{
    memset(dp,-1,sizeof(dp));
    n=gi();k=gi();
    fp(i,1,n) a[i].dat=gi();fp(i,1,n) a[i].w=gi(),o[i]=a[i].w;fp(i,1,n) a[i].v=gi();
    //len=unique(o+1,o+1+n)-o-1;
    //fp(i,1,n) a[i].w=lower_bound(o+1,o+1+len,a[i].w)-o;
    sort(a+1,a+1+n);
    fp(i,1,n) b[i].w=a[i].w,b[i].id=i;
    sort(b+1,b+1+n);
    fp(i,1,n) a[b[i].id].w=i;
    fp(i,1,n) s[i]=s[i-1]+a[i].v;
    //这里不要预处理dp[l][r][w]=k之类，上面能处理
    printf("%lld\n",dfs(1,n,1));
    return 0;
}