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; }
|
近期评论