#2009. 「SCOI2015」小凸玩密室

神仙题啊。完全想不出

首先看方案。可以从任意一个点开始,在这个点要先走完子树,然后走到父亲,再走兄弟,再走父亲的父亲,父亲的兄弟。。一直走到1,1的另外一个子树,结束。

完全不会鸭.jpg

设f[i][j]是走完i的子树,再走到i的第j个祖先的最小花费。那么上面的方案可以表示成:f[x][1](走完x的子树再走到x父亲)+(x父亲~x兄弟)+f[(x兄弟)][1](x兄弟走完了走到x父亲的父亲)+...

那么怎么求f呢,感觉不是很好求

再来一个:g[i][j]是走完i的子树,再走到i的第j个祖先的兄弟的最小花费。

那么就很好转移了,分情况讨论即可,不难,见代码



#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il int gi(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
ll a[200010],b[200010],dep[200010];
ll w[200010][19];//w[i][j]是i到i的第j个祖先的距离
ll f[200010][19],g[200010][19];
int main(){
#ifndef ONLINE_JUDGE
freopen("4253.in","r",stdin);
freopen("4253.out","w",stdout);
#endif
int n=gi();
for(int i=1;i<=n;++i)a[i]=gi();
for(int i=2;i<=n;++i)b[i]=gi();
for(int i=1;i<=n;++i){
dep[i]=dep[i>>1]+1;
w[i][1]=b[i];
for(int j=2;j<=dep[i] ;++j)
w[i][j]=w[i>>1][j-1]+b[i];
}
for(int i=n;i;--i){
for(int j=0;j<=dep[i];++j){
if((i<<1|1)<=n){// 2个儿子,要枚举先走到哪一个儿子去
f[i][j]=std::min(g[i<<1][0]+b[i<<1]*a[i<<1]+f[i<<1|1][j+1],g[i<<1|1][0]+b[i<<1|1]*a[i<<1|1]+f[i<<1][j+1]);
g[i][j]=std::min(g[i<<1][0]+b[i<<1]*a[i<<1]+g[i<<1|1][j+1],g[i<<1|1][0]+b[i<<1|1]*a[i<<1|1]+g[i<<1][j+1]);
}else if((i<<1)<=n){// 1个儿子,直接走到这个儿子然后继续
f[i][j]=f[i<<1][j+1]+b[i<<1]*a[i<<1];
g[i][j]=g[i<<1][j+1]+b[i<<1]*a[i<<1];
}else{// 叶子,子树走完了可以直接跳到j所指向的点
f[i][j]=w[i][j]*a[i>>j];
g[i][j]=(w[i][j+1]+b[(i>>j)^1])*a[(i>>j)^1];
}
}
}
ll ans=2e18;
for(int i=1;i<=n;++i){//枚举起点
ll res=f[i][1];//先走完i的子树,然后走到i的父亲
for(int j=i>>1,lst=i;j;lst=j,j>>=1){
if((lst^1)<=n)res+=b[lst^1]*a[lst^1]+f[lst^1][2];
else res+=b[j]*a[j>>1];
}
ans=std::min(ans,res);
}
printf("%lld\n",ans);
return 0;
}
上一篇:Appium+python的单元测试框架unittest(1)(转)


下一篇:linux下面实时查看进程,内存以及cpu使用情况使用命令