loj#2009.「SCOI2015」小凸玩密室

题目链接

loj#2009. 「SCOI2015」小凸玩密室

题解

树高不会很高<=20

点亮灯泡x,点亮x的一个子树，再点亮x另外的子树，

然后回到x的父节点，点亮父节点之后再点亮父节点的其他子树

所以对于一个节点x，有这样两种情况

x还没有被点亮，那么下一个被点亮的是x的一个儿子

x是叶子节点，那么下一个被点亮的是它的祖先，或者是它祖先的儿子

设f[i][j]表示点亮i之后回到i的第j个祖先的最小花费

设g[i][j]表示点亮i之后回到i的第j个祖先的另一个儿子的最小花费

然后从下到上，由儿子的状态转移到父亲的状态

讨论一下儿子个数

最后模拟点亮过程统计答案

ans要开大

代码

#include<cstdio>

#include<algorithm>

using namespace std;

inline int read() {

    int x = 0,f = 1;

    char c = getchar();

    while(c < '0' || c > '9')c = getchar();

    while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();

    return x * f ;

}

#define INF 2000000000000000000ll

#define LL long long

#define fa(i,j) ((1 << j - 1) <= i ? (i >> j) : -1 )

#define bro(i,j) ((i >> j - 1) ^ 1)

#define ls (i << 1)

#define rs (i << 1 | 1)

const int maxn = 200007;

int n;

LL a[maxn],dp[maxn][27][2],dis[maxn][27];

int main() {

   	n = read();

    for(int i = 1;i <= n;++ i) a[i] = read();

    dis[1][1] = 0;

    for(int i = 2;i <= n;++ i) {

        dis[i][1] = read();

        for(int j = 2;~fa(i,j);++ j)  dis[i][j] = dis[fa(i,1)][j - 1] + dis[i][1];

    }

    for(int i = n;i >= 1;-- i) { for(int j = 1;~ fa(i,j);++ j) {

        dp[i][j][0] = dp[i][j][1] = INF;

        if(ls > n)

            dp[i][j][0] = dis[i][j] * a[fa(i,j)], dp[i][j][1] = (dis[i][j] + dis[bro(i,j)][1]) * a[bro(i,j)];

    	else if(rs > n)

            dp[i][j][0] = dp[ls][j + 1][0] + dis[ls][1] * a[ls], dp[i][j][1] = dp[ls][j + 1][1] + dis[ls][1] * a[ls];

        else

            dp[i][j][0] = min(dp[i][j][0],dp[ls][1][1] + dp[rs][j + 1][0] + dis[ls][1] * a[ls]),

            dp[i][j][0] = min(dp[i][j][0],dp[rs][1][1] + dp[ls][j + 1][0] + dis[rs][1] * a[rs]),

        	dp[i][j][1] = min(dp[i][j][1],dp[ls][1][1] + dp[rs][j + 1][1] + dis[ls][1] * a[ls]),

            dp[i][j][1] = min(dp[i][j][1],dp[rs][1][1] + dp[ls][j + 1][1] + dis[rs][1] * a[rs]);

        }

    }

    LL ans = INF;

    for(int x = 1;x <= n;x ++) {

        LL tmp = dp[x][1][0];

        for(int i = fa(x,1),last = x;~i;i = fa(i,1),last = fa(last,1)) {

            if(bro(last,1) <= n)  tmp += dis[bro(last,1)][1] * a[bro(last,1)] + dp[bro(last,1)][2][0];

            else tmp +=  dis[i][1] * a[fa(i,1)];

        }

        ans = min(ans,tmp);

    }

    printf("%lld\n",ans);

    return 0;

}