题目链接

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; }

转载于:https://www.cnblogs.com/sssy/p/9602898.html

相关资源：25个经典网站源代码