BZOJ4446: [Scoi2015]小凸玩密室

用u_i,j表示走完i的子树后走到i的深度为j的祖先的兄弟的最小代价；

用v_i,j表示走完i的子树后走到i的深度为j的祖先的最小代价，用u算出v。

枚举起点，计算答案。

#include<algorithm>
#include<cstdio>
using std::min;
typedef long long ll;
const int N=2e5+5;
ll a[N],b[N],c[N],f[N][19][2];
int main(){
	struct{
		operator int(){
			int x=0,c=getchar();
			while(c<48)c=getchar();
			while(c>47)
				x=x*10+c-48,c=getchar();
			return x;
		}
	}it;
	int n=it;
	for(int i=1;i<=n;++i)
		a[i]=it;
	for(int i=2;i<=n;++i){
		b[i]=it;
		c[i]=c[i>>1]+b[i];
	}
	for(int i=n;i;--i)
		for(int j=1;i>>j-1;++j)
			if(i<<1>n){
				f[i][j][0]=(c[i]-c[i>>j]+b[i>>j-1^1])*a[i>>j-1^1];
				f[i][j][1]=(c[i]-c[i>>j])*a[i>>j];
			}else{
				f[i][j][0]=i<<1<n?min(b[i<<1]*a[i<<1]+f[i<<1][1][0]+f[i<<1^1][j+1][0],b[i<<1^1]*a[i<<1^1]+f[i<<1^1][1][0]+f[i<<1][j+1][0]):b[i<<1]*a[i<<1]+f[i<<1][j+1][0];
				f[i][j][1]=i<<1<n?min(b[i<<1]*a[i<<1]+f[i<<1][1][0]+f[i<<1^1][j+1][1],b[i<<1^1]*a[i<<1^1]+f[i<<1^1][1][0]+f[i<<1][j+1][1]):b[i<<1]*a[i<<1]+f[i<<1][j+1][1];
			}
	if(~n&1)
		f[n^1][2][1]=b[n>>1]*a[n>>2];
	ll z=1e18;
	for(int i=n;i;--i){
		ll s=f[i][1][1];
		for(int j=i;j>>1;j>>=1)
			s+=b[j^1]*a[j^1]+f[j^1][2][1];
		z=min(z,s);
	}
	printf("%lld
",z);
}

BZOJ4446: [Scoi2015]小凸玩密室

相关推荐