最优排序二叉树问题OBST【区间dp+四边形不等式优化】

题目大意

给定n个点的权值，要求构建一棵二叉搜索树，使得他满足 ,权值乘以深度的和最小

题目分析

这个题目，我们通过BST的构建，由于BST 的性质可知，根节点的左边一定小于根，右边一定大于根，所以先对所有数据排序，然后枚举根节点。根节点对于答案的贡献 fk*1，由于第k个结点作为根节点了，因此对于其他结点来说，他们的深度都增加了一个，所以，他们都对答案的贡献增加 fi
而根节点将所有数据分成两部分（1-k-1）, （k+1,n） 因此我们枚举 dp[i][j] 表示从i,j这一串数据构成的二叉树的最小值
dp[i][j] = min(dp[i][k-1]+dp[k+1][j]+w[i][k-1]+w[k+1][j],dp[i][j]);
其中 w[i][j] 表示从i到j的数据之和。

此题还可以用四边形不等式加速

代码详解

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
#define sc(x) scanf("%d",&x)
#define pt(x) printf("%d\n",x)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=1e5+50;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
typedef long long ll;
ll dp[300][300];
ll k[300][300];
ll f[300];
ll ans=0;
ll w[300];
ll getinv(int x,int y)
{
    if(x>y) return 0;
    return w[y]-w[x-1];
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        ans=0;
         cl(dp); cl(k);cl(f);cl(w);
       for(int i=1;i<=n;i++)
       {
           scanf("%lld",&f[i]);
           w[i]=w[i-1]+f[i];
       }
       for(int i=1;i<=n;i++)
       {
           for(int j=i+1;j<=n;j++)
           {
               dp[i][j]=1e18;
           }
       }
       for(int i=1;i<=n;i++) {k[i][i]=i;dp[i][i] =0;}
       for(int len = 1;len<=n;len++)
       {
           for(int i=1;i+len<=n;i++)
           {
               int j= i+len;
              // cout<<i<<" "<<j<<endl;
               for(int t = k[i][j-1];t<=k[i+1][j];t++)
               {
                 // cout<<t<<endl;
                  ll tmp = dp[i][t-1]+dp[t+1][j]+getinv(i,t-1)+getinv(t+1,j);
                  //tmp +=dp[i][t-1]+dp[t+1][j];
                  //cout<<dp[i][t-1]<<" "<<dp[t+1][j]<<" "<<tmp<<endl;
                  if(dp[i][j]>=tmp)
                  {
                      k[i][j] = t;
                      dp[i][j]=tmp;
                  }
               }
           }
       }
       printf("%lld\n",dp[1][n]);
    }
    return 0;
}
/* 1 5 3 10 10 10 3 5 10 20 */