这道题实在太苟了。
因为不知道$dist(u,v)$的$u$从子树的哪个位置来,但确定一定是某一个叶子节点。
还要处理是哪个子树先进行,好烦啊。。。
那就预处理一下叶子结点吧,有状态$f_{i,j,0}$表示从$i$号叶子结点返回到它的第$j$个祖先(未点灯)的费用。
这个不难处理$f_{i,j,0}=dist(i,p_{i,j})*a_{p_{i,j}}$
从一个子树中出来,进到另一个子树的情况把它简化成两个叶子结点之间的转移。
有$f_{i,j,1}$表示从$i$号叶子结点返回到它的第$j$个祖先(未点灯)的另一个儿子的费用
这个也不难,所以不写了。
好了,现在有两棵子树$ls,rs$,根节点$i$。
根据$DP$的思想,现在已经处理好了$ls,rs$的状态。
如果根节点要返回到第$j$个祖先,那么返回的起点就一定来自于左子树,或者右子树的某一个叶子结点。
根据之前的预处理,就可以联想到根节点的状态如何定义与转移。
$f_{i,j,0}$表示已经处理好了以$i$为根的子树,且返回到它的第$j$个祖先的费用
$f_{i,j,1}$同理,具体方程见代码。
但是,
这道题还有一个坑点,并没确定哪个是第一个点亮的。
所以还需要进行一些操作。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int N=2e5+5,mod=20170408;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>
void qw(o x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
ll f[N][19][2],d[N][19],b[N],a[N];int Log[N];int n;
void dp()
{
for(int i=n;i;i--)
for(int j=1;j<=Log[i];j++)
{
int w=(i>>(j-1))^1;
if((i<<1)>n)
{
f[i][j][0]=d[i][j]*a[i>>j];
f[i][j][1]=(d[i][j]+d[w][1])*a[w];
}
else if(((i<<1)|1)>n)
{
int ls=i<<1;
f[i][j][0]=f[ls][j+1][0]+d[ls][1]*a[ls];
f[i][j][1]=f[ls][j+1][1]+d[ls][1]*a[ls];//要下去到ls,也要算上。
}
else
{
int ls=i<<1,rs=i<<1|1;
f[i][j][0]=min(f[ls][j+1][0]+f[rs][1][1]+d[rs][1]*a[rs],f[rs][j+1][0]+f[ls][1][1]+d[ls][1]*a[ls]);
f[i][j][1]=min(f[ls][j+1][1]+f[rs][1][1]+d[rs][1]*a[rs],f[rs][j+1][1]+f[ls][1][1]+d[ls][1]*a[ls]);
}
}
ll ans=0x3f3f3f3f3f3f3f3f;
for(int i=1;i<=n;i++)
{
ll tmp=f[i][1][0];int t=1;
for(int x=i>>1,lst=i;t<=Log[i];lst=x,x=x>>1)
{
int w=lst^1;++t;
if(w<=n)tmp+=d[w][1]*a[w]+f[w][2][0];//如果有,那就继承。
else tmp+=d[x][1]*a[x>>1];//如果没有,让x上去,因为x是最后点亮那个
}
ans=min(tmp,ans);
}
qw(ans);puts("");
}
int main()
{
qr(n);
for(int i=1;i<=n;i++)Log[i]=Log[i>>1]+1;
for(int i=1;i<=n;i++)qr(a[i]);
for(int i=2;i<=n;i++)qr(b[i]);
for(int i=2;i<=n;i++)
for(int j=1;j<Log[i];j++)
d[i][j]=d[i>>1][j-1]+b[i];
dp();
return 0;
}
最后一次更新于2020-04-02
0 条评论