ccpc

链接:https://www.zhixincode.com/contest/1/problem/E?problem_id=16
思路:易证这是一个树,所以我们考虑树上dp即可,枚举当前点选或者不选,对子树造成不同影响,然后dp子树转移即可

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

using namespace std;

const int maxn = 1000;
int dp[maxn][2];
vector<int> G[maxn];
int n;
int f[maxn],d[maxn];
bool vis[maxn][2];
bool ok[maxn];

int (int u,int ff,int k){
if(vis[u][ff])return dp[u][ff];
vis[u][ff] = 1;
int res = 0;
if(ff)res = f[u]-d[min(u,k)];
else res = f[u];

for(int i=0;i<G[u].size();i++){
int v = G[u][i];
if(v==k)continue;
res+=dfs(v,1,u);
}
int ans = 0;
for(int i=0;i<G[u].size();i++){
int v = G[u][i];
if(v==k)continue;
ans+=dfs(v,0,u);
}
ok[u] = 1;
return dp[u][ff] = max(res,ans);
}

int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&f[i]);
for(int i=1;i<=n;i++)scanf("%d",&d[i]);
for(int i=2;i<=n;i++){
if(i%2&&3*i+1<=n){
G[i].push_back(3*i+1);
G[3*i+1].push_back(i);
}
if(i%2==0){
G[i].push_back(i/2);
G[i/2].push_back(i);
}
}
int res = 0;
for(int i=1;i<=n;i++){
if(!ok[i])res+=dfs(i,0,i);
}
printf("%dn",res);
return 0;
}