题目大意：

给定一棵严格的treap，父亲节点的优先级必然小于儿子节点的。权值按照二叉树的定义，左儿子小于父亲小于右儿子。

深度从1开始定义，每个点除优先级、数值之外，还有一个访问频度。

访问频度所产生的代价是：访问频度*该点深度（这和事实相符）

可以用给定的k的代价，修改任意个点的优先级为任意实数（当然，修改优先级，树的形态，各点深度就可能变化了）

最终的总代价为：频度产生代价+修改代价。

最小化这个总代价。

N<=70，1<=K<=30000000

分析：

平衡树是一个动态的数据结构，难以抓住形态的变化，也不方便记录深度之类。所以必须抓住不变的量当做突破口。

不管平衡树怎么转，根据二叉树的定义，它的中序遍历一定是不变的。

所以我们可以找到这棵树的中序遍历，就把这棵树变成了一个静态的区间，只不过每个区间所代表的点的优先级可能会变。

发现，每一个连续的子区间，都对应treap的连续一部分。可以把小的区间先建树，再把大的区间用小的区间合并。我们合并的时候枚举的划分点，就是这部分treap的树根

区间DP顺理成章。

除了f[l][r]之外，为了维护优先级的关系，必然要再记录一维。

发现，只要根节点的优先级确定，子树的优先级的范围就确定了。

所以考虑记录根节点优先级。（这里优先级只考虑相对大小，而且范围又大，所以要离散化为1~n）

但是，朴素的f[l][r][w]中，w单单记录根节点优先级的话，由于子树所有大于w的都可以转移，还要for一遍。状态n^3,转移n^2，会爆。

所以，我们令f[l][r][w]表示，将l~r这段区间建成treap，其中根节点优先级大于等于w的最小代价。

根据枚举的根节点是否修改，可以设计转移方程是：

修改：

f[l][r][w]=min(f[l][r][w],f[l][k-1][w]+f[k+1][r][w]+K+sum[r]-sum[l-1])  ————其中，sum[i]表示，区间中，1~i的访问频度和

当划分点的优先级ch[k]大于w时，可以不修改。

f[l][r][w]=min(f[l][r][w],f[l][k-1][ch[k]]+f[k+1][r][ch[k]]+sum[r]-suim[l-1])

最后答案就是：f[1][n][1];

注意，o循环的时候，必须倒序！！因为ch[k]>=o时候，要从o更大的地方获取最小值，必须先把o较大的处理完。

代码1（未简化）：

#include
     
      using namespace std;typedef long long ll;const int N=77;const ll inf=2e18;ll f[N][N][N];int n;ll m;int a[N];int tot;int w[N],p[N],d[N];int prio[N];ll sum[N];int ch[N];//离散化后的优先级 bool cmp(int a,int b){    return w[a]
      
       =1;k--)     {         if(k<=ch[i]) f[i][i][k]=d[a[i]];         else f[i][i][k]=d[a[i]]+m;//注意，k>ch的时候，不一定是+oo，可以通过修改改变      }//l=1的初值         for(int i=1;i<=n;i++)     sum[i]=sum[i-1]+d[a[i]];//前缀和     for(int l=2;l<=n;l++)     for(int i=1;i<=n;i++)    {        int j=l+i-1;        if(j>n) break;        if(l==2)//长度为二的时候，只能二并一         {           for(int o=n;o>=1;o--)            {                f[i][j][o]=min(f[i][j][o],f[i][i][o]+m+sum[j]-sum[i-1]);                f[i][j][o]=min(f[i][j][o],f[j][j][o]+m+sum[j]-sum[i-1]);                if(ch[i]>=o) f[i][j][o]=min(f[i][j][o],f[i][i][ch[i]]+f[j][j][ch[i]]+sum[j]-sum[i-1]-d[a[i]]);                if(ch[j]>=o) f[i][j][o]=min(f[i][j][o],f[i][i][ch[j]]+f[j][j][ch[j]]+sum[j]-sum[i-1]-d[a[j]]);            }        }        else{           for(int o=n;o>=1;o--)            for(int k=i;k<=j;k++)           {                if(k==i)//k在端点处，只能用端点和右边所有部分合并                 {                    f[i][j][o]=min(f[i][j][o],f[i+1][j][o]+m+sum[j]-sum[i-1]);                    if(ch[i]>=o) f[i][j][o]=min(f[i][j][o],f[i][i][ch[i]]+f[i+1][j][ch[i]]+sum[j]-sum[i-1]-d[a[i]]);             }             else if(k==j)//同理              {                 f[i][j][o]=min(f[i][j][o],f[i][j-1][o]+m+sum[j]-sum[i-1]);                 if(ch[j]>=o) f[i][j][o]=min(f[i][j][o],f[i][j-1][ch[j]]+f[j][j][ch[j]]+sum[j]-sum[i-1]-d[a[j]]);             }             else{
   //正宗转移方程                  f[i][j][o]=min(f[i][j][o],f[i][k-1][o]+f[k+1][j][o]+m+sum[j]-sum[i-1]);                 if(ch[k]>=o) f[i][j][o]=min(f[i][j][o],f[i][k-1][ch[k]]+f[k+1][j][ch[k]]+sum[j]-sum[i-1]);             }           }        }    }    printf("%lld",f[1][n][1]);    return 0;}
      
     

太恶心了。为了保证l<=r，做出了巨大的讨论。

其实不用这么麻烦，只要让l>r的时候，赋值为0就好，相当于不存在。根本不影响答案。

代码2（化简）

#include
     
      using namespace std;typedef long long ll;const int N=77;const ll inf=2e18;ll f[N][N][N];int n;ll m;int a[N];int tot;int w[N],p[N],d[N];int prio[N];ll sum[N];int ch[N];//离散化后的优先级 bool cmp(int a,int b){    return w[a]
      
       =1;o--)     for(int i=n;i>=1;i--)      for(int j=i;j<=n;j++)        for(int k=i;k<=j;k++)         {          f[i][j][o]=min(f[i][j][o],f[i][k-1][o]+f[k+1][j][o]+m+sum[j]-sum[i-1]);          if(ch[k]>=o) f[i][j][o]=min(f[i][j][o],f[i][k-1][ch[k]]+f[k+1][j][ch[k]]+sum[j]-sum[i-1]);        }//不放心，可以考虑代入长度小于等于2的情况。0的作用就出来了。         //连初始化l=1都省了。     printf("%lld",f[1][n][1]);    return 0;}
      
     

总结：

1.对于琢磨不透的变化，一定有不变的东西。一定要抓住其中的不变量，作为突破口。

2.循环顺序要注意，一个是不能有后效性，一个是要保证能影响到这个状态的所有状态都处理完了。

3.注意考虑清楚所有可能转移的方式。