LeetCode Weekly Contest 369 4問目 - Maximum Points After Collecting Coins From All Nodes [2920]

Source

LeetCode Weekly Contest 369
問題文

問題概要

省略

解法

省略

cLay（version 20231031-1）のコード

C++に変換後のコードはこちら

#define main dummy_main
{}
#undef main

graph g;
int C[1d5];
int N, a[1d5], b[1d5], K;
int dp[1d5][15];

int solve(int a, int m){
  int r1, r2;

  if(m >= 15) return 0;
  if(dp[a][m] >= 0) return dp[a][m];

  r1 = (C[a]>>m) - K;
  r2 = (C[a]>>m) / 2;
  rep[g.edge[a]](i,g.es[a]){
    r1 += solve(i,m);
    r2 += solve(i,m+1);
  }

  return dp[a][m] = max(r1, r2);
}

class Solution {
public:
  int maximumPoints(VVI &edges, VI &coins, int k) {
    dummy_main();

    K = k;
    N = vec2arr(coins, C);
    vec2arr(edges, a, b);
    g.setEdgeRootedTree(N,N-1,a,b);

    rep(i,N) rep(j,15) dp[i][j] = -1;
    return solve(0,0);
  }
};

Current time: 2024年05月05日17時51分53秒
Last modified: 2023年10月31日21時49分07秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)