C++14(g++5.4) 解法, 执行用时: 69ms, 内存消耗: 4296K, 提交时间: 2019-11-30 20:05:18

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rint register int
#define min(a,b) (a<b? a:b)
using namespace std;
struct node{int x,y,z;}a[100];
int f[100][100][100];
int n,K;
inline int read()
{
    int w=1,ans=0;
    char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') w=-1; ch=getchar();}
    while(isdigit(ch)) {ans=(ans<<3)+(ans<<1)+(ch^48); ch=getchar();}
    return ans*w;
}
inline bool cmp(node a,node b)
{
    return a.y<b.y;
}
inline bool cmp2(node a,node b)
{
    return a.x<b.x;
}
int main()
{
    //freopen("tree.in","r",stdin);
    //freopen("tree.out","w",stdout);
    n=read();K=read();
    for (int i=1;i<=n;i++) a[i].x=read();//数据
    for (int i=1;i<=n;i++) a[i].y=read();//权值
    for (int i=1;i<=n;i++) a[i].z=read();//访问频度
    sort(a+1,a+n+1,cmp);//按权值排序，离散化
    for (int i=1;i<=n;i++) a[i].y=i;//将权值离散化
    sort(a+1,a+n+1,cmp2);
    for (int i=1;i<=n;i++) a[i].z+=a[i-1].z;//前缀和
    memset(f,0x7f,sizeof f);
    for (int i=1;i<=n+1;i++)
     for (int w=0;w<=n;w++)
      f[i][i-1][w]=0;
       
    for (rint w=n;~w;w--)//~w指w非零，区间内所有权值大于w
     for (rint i=n;i;i--)
      for (rint j=i;j<=n;j++)
       for (rint k=i;k<=j;k++)//区间dp枚举根节点位置
       {
         if (a[k].y>=w)
          f[i][j][w]=min(f[i][j][w],f[i][k-1][a[k].y]+f[k+1][j][a[k].y]+a[j].z-a[i-1].z);
          //a[j].z-a[i-1].z：当树深加1，把每个访问频度都再加一次
         f[i][j][w]=min(f[i][j][w],f[i][k-1][w]+f[k+1][j][w]+a[j].z-a[i-1].z+K);
       }
    printf("%d",f[1][n][1]);
    return 0;   
}

C++(clang++ 11.0.1) 解法, 执行用时: 25ms, 内存消耗: 4324K, 提交时间: 2022-10-02 18:27:51

#include<bits/stdc++.h>
#define min(a,b) (a<b? a:b)
using namespace std;
struct node{int x,y,z;}a[100];
int f[100][100][100],n,K;
inline int read(){
    int w=1,ans=0;
    char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') w=-1; ch=getchar();}
    while(isdigit(ch)) {ans=(ans<<3)+(ans<<1)+(ch^48); ch=getchar();}
    return ans*w;
}
inline bool cmp(node a,node b){return a.y<b.y;}
inline bool cmp2(node a,node b){return a.x<b.x;}
int main(){
    n=read(),K=read();
    for (int i=1;i<=n;i++) a[i].x=read();
    for (int i=1;i<=n;i++) a[i].y=read();
    for (int i=1;i<=n;i++) a[i].z=read();
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=n;i++) a[i].y=i;
    sort(a+1,a+n+1,cmp2);
    for (int i=1;i<=n;i++) a[i].z+=a[i-1].z;
    memset(f,0x7f,sizeof f);
    for (int i=1;i<=n+1;i++)for (int w=0;w<=n;w++)f[i][i-1][w]=0;
    for (int w=n;~w;w--)
        for (int i=n;i;i--)
            for (int j=i;j<=n;j++)
                for (int k=i;k<=j;k++){
                    if (a[k].y>=w)f[i][j][w]=min(f[i][j][w],f[i][k-1][a[k].y]+f[k+1][j][a[k].y]+a[j].z-a[i-1].z);
                    f[i][j][w]=min(f[i][j][w],f[i][k-1][w]+f[k+1][j][w]+a[j].z-a[i-1].z+K);
                }
    printf("%d",f[1][n][1]);
    return 0;   
}