[HNOI2018] 道路

YoungNeal 2018-07-27 原文

Description

给一棵二叉树，每个叶子节点 $i$ 有三个属性 $a_i,b_i,c_i$

每个非叶子节点都能标记向左右儿子中的一条边(记作 $x$ 边和 $y$ 边)

设叶子节点 $i$ 到根的路径上有 $p$ 条没被标记的 $x$ 边，$q$ 条没被标记的 $y$ 边

那么 $i$ 的花费就是 $c_i\times (a_i+p)\times (b_i+q)$

最小化这个花费

Solution

传说中的pj难度题

这个式子有点吓人啊

定义 $f[i][j][k]$ 表示 $i$ 到根的路径上，有 $j$ 条没被标记的 $x$ 边， $k$ 条没被标记的 $y$ 边 $i$ 的最小花费

对于叶子节点，直接枚举 $x$ 和 $y$ 边各有多少条

对于非叶节点，左右儿子选择一条标记取最小值就行了

等等，我们来算一下空间复杂度

第一维要开 $2n$，第二第三维至少要开 $41$，又因为答案会爆 $int$，所以要开 $long\;long$

那么光 $f$ 数组的空间占用就是 $40010*1600*8/1024/1024 \approx 488M$，显然不够用

我们考虑二叉树的性质，一个点的 $f$ 值只用知道它的左右儿子的 $f$ 值即可，又因为最多只有 $\log n$ 层，所以我们动态分配内存，这样下来空间复杂度就是 $O(\log n*1600)$ 了。

Code

#include<cstdio>
#include<cctype>
#include<cstring>
#define N 20005
#define in inline
typedef long long ll;
#define re register signed
#define min(A,B) ((A)<(B)?(A):(B))
#define max(A,B) ((A)>(B)?(A):(B))
#define swap(A,B) ((A)^=(B)^=(A)^=(B))
//一颗二叉树  f[i][j][k]->refers from 1 to i,still has j highway,k railway,mininum cost
int n,cnt;
int ch[N][2];
int stk[N],top;
ll f[100][45][45];
int a[N],b[N],c[N];
int hi[N<<1],ri[N<<1];
//要压空间 sb题
//开栈 最多logn
in int getint(){
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) f|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
in int newnode(){
    return top?stk[top--]:++cnt;
}
void dp(int now,int d,int k){
    if(now>n){
        for(int i=0;i<=hi[now];i++){
            for(int j=0;j<=ri[now];j++)
                f[k][i][j]=(ll)c[now-n]*(a[now-n]+i)*(b[now-n]+j);
        }
        return;
    }
    int x=newnode();
    int y=newnode();
    dp(ch[now][0],0,x);
    dp(ch[now][1],1,y);
    for(re i=0;i<=hi[now];i++){
        for(re j=0;j<=ri[now];j++)
            f[k][i][j]=min(f[x][i][j]+f[y][i][j+1],f[x][i+1][j]+f[y][i][j]);
    }
    stk[++top]=x;stk[++top]=y;
   /* puts("");
    printf("now=%d\n",now);
    for(int i=0;i<=hi[now];i++){
        for(int j=0;j<=ri[now];j++)
            printf("i=%d,j=%d,f=%lld\n",i,j,f[k][i][j]);
    }*/
}
void dfs(int now,int x,int y){
    if(now>n){hi[now]=x;ri[now]=y;return;}
    if(ch[now][0]) dfs(ch[now][0],x+1,y);
    if(ch[now][1]) dfs(ch[now][1],x,y+1);
    hi[now]=x;ri[now]=y;
}
signed main(){
    n=getint();
    for(re i=1;i<n;i++){
        int x=getint(),y=getint();
        if(x<0) x=n-x;
        if(y<0) y=n-y;
        ch[i][0]=x;ch[i][1]=y; //leftson->highway  rightson->railway
    }
    for(re i=1;i<=n;i++)
        a[i]=getint(),b[i]=getint(),c[i]=getint();
    dfs(1,0,0);
    int x=newnode();
    dp(1,0,x);
    printf("%lld\n",f[x][0][0]);
    return 0;
}