给一棵二叉树，每个叶子节点 \(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; }