做题&学习记录（2月）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 const int MAXN = 200010;
 6 #define p(i, j) (((1 << (j - 1)) <= i) ? (i >> j) : -1)
 7 #define b(i, j) ((i >> (j - 1)) ^ 1)
 8 #define ls (i << 1)
 9 #define rs (i << 1 | 1)
10 
11 int n; ll num[MAXN];
12 ll dis[MAXN][20], dp[MAXN][20][2];
13 
14 int main()
15 {
16     scanf("%d", &n);
17     for(int i = 1; i <= n; ++i) scanf("%lld", &num[i]);
18     for(int i = 2; i <= n; ++i)
19     {
20         scanf("%lld", &dis[i][1]);
21         for(int j = 2; ~p(i, j); ++j) dis[i][j] = dis[i][1] + dis[p(i, 1)][j - 1];
22     }
23     for(int i = n; i; --i)
24         for(int j = 1; ~p(i, j); ++j)
25         {
26             dp[i][j][0] = dp[i][j][1] = 0x3f3f3f3f3f3f3f3f;
27             int lson = ls, rson = rs;
28             if((i << 1) > n)
29             {
30                 dp[i][j][0] = dis[i][j] * num[p(i, j)];
31                 dp[i][j][1] = (dis[i][j] + dis[b(i, j)][1]) * num[b(i, j)];
32             }
33             else if((i << 1 | 1) > n)
34             {
35                 dp[i][j][0] = dis[ls][1] * num[ls] + dp[ls][j + 1][0];
36                 dp[i][j][1] = dis[ls][1] * num[ls] + dp[ls][j + 1][1];
37             }
38             else
39             {
40                 dp[i][j][0] = min(dp[i][j][0], dis[ls][1] * num[ls] + dp[ls][1][1] + dp[rs][j + 1][0]);
41                 dp[i][j][0] = min(dp[i][j][0], dis[rs][1] * num[rs] + dp[rs][1][1] + dp[ls][j + 1][0]);
42                 dp[i][j][1] = min(dp[i][j][1], dis[ls][1] * num[ls] + dp[ls][1][1] + dp[rs][j + 1][1]);
43                 dp[i][j][1] = min(dp[i][j][1], dis[rs][1] * num[rs] + dp[rs][1][1] + dp[ls][j + 1][1]);
44             }
45         }
46     ll ans = 0x3f3f3f3f3f3f3f3f;
47     for(int s = 1; s <= n; ++s)
48     {
49         ll tmp = dp[s][1][0];
50         for(int i = p(s, 1), lst = s; ~i; i = p(i, 1), lst = p(lst, 1))
51         {
52             if(b(lst, 1) <= n) tmp += dis[b(lst, 1)][1] * num[b(lst, 1)] + dp[b(lst, 1)][2][0];
53             else tmp += dis[i][1] * num[p(i, 1)];
54         }
55         ans = min(ans, tmp);
56     }
57     printf("%lld\n", ans);
58     return 0;
59 }