Luogu

分析

首先应该可以一眼看出来这就是个 treap，然后改权值就相当于旋转。

考虑到 treap 旋转后中序遍历是不变的，因此我们可以先给所有节点按数据值排个序，这样就能得到中序遍历了。

进一步发现，中序遍历中一段区间在 treap 上是连通的一部分。因此可以考虑区间 DP。

设 $dp_{i,j,k}$ 表示 $[i,j]$ 内的节点，根节点权值 $\geq k$ 的最小代价。因为 $k$ 一维很大，所以我们提前将权值离散化。

转移时枚举一个根节点 $l$，然后有两种转移：

• 更改根节点的权值：$dp_{i,l-1,k}+dp_{l+1,j,k}+K+sum(i,j)\to dp_{i,j,k}$。
• 不更改根节点的权值：$dp_{i,l-1,w_l}+dp_{l+1,r,w_l}+sum(i,j)\to dp_{i,j,k}$。

这里的 $sum(i,j)$ 表示 $[i,j]$ 内节点的访问频度之和，$w_l$ 表示 $l$ 的权值。

使用记搜转移即可。答案为 $dp_{1,n,1}$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=70+10;
const int inf=0x3f3f3f3f;

int n,K;
struct node { int d,w,f; } a[N];
bool operator <(node a,node b) { return a.d<b.d; }
int S[N],sum[N];
int dp[N][N][N];

inline int dfs(int l,int r,int k) {
    if (l>r) return 0;
    if (dp[l][r][k]!=inf) return dp[l][r][k];
    int& res=dp[l][r][k];
    for (re int i=l;i<=r;++i) {
        res=min(res,dfs(l,i-1,k)+dfs(i+1,r,k)+K);
        if (a[i].w>=k) res=min(res,dfs(l,i-1,a[i].w)+dfs(i+1,r,a[i].w));
    }
    return res+=sum[r]-sum[l-1];
}

int main() {
    n=read(),K=read();
    for (re int i=1;i<=n;++i) a[i].d=read();
    for (re int i=1;i<=n;++i) S[i]=a[i].w=read();
    sort(S+1,S+n+1); unique(S+1,S+n+1);
    for (re int i=1;i<=n;++i) a[i].w=lower_bound(S+1,S+n+1,a[i].w)-S;
    for (re int i=1;i<=n;++i) a[i].f=read();
    sort(a+1,a+n+1);
    for (re int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i].f;
    memset(dp,0x3f,sizeof(dp)); printf("%d\n",dfs(1,n,1));
    return 0;
}