Codeforces Round #595 DIV3 F問題 - Maximum Weight Subset

Source

Codeforces Round #595 DIV3 F問題
Problem description

問題概要

省略

解法

省略

cLay（version 20191110-1）のコード

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

//no-unlocked
int N, K, U[200], V[200];
int A[200], AA[200], cnv[200];

graph g;
int dp[200][202];

{
  int i, j, k, x, y, res, tmp, mx;

  rd(N,K++,AA(N),(U--,V--)(N-1));
  g.setEdgeRootedTree(N,N-1,U,V,0,1,cnv);
  rep(i,N) A[i] = AA[cnv[i]];

  rrep(i,N) rrep(k,K+1){
    dp[i][k] = 0;
    if(k < K) dp[i][k] = dp[i][k+1];
    if(k == 0) dp[i][k] >?= dp[i][K] + A[i];

    x = max(k-1, 0);
    y = max(x, K - x - 2);
    mx = tmp = 0;
    rep[g.edge[i]](j,g.es[i]){
      tmp += dp[j][y];
      mx >?= dp[j][x] - dp[j][y];
    }
    dp[i][k] >?= tmp + mx;
  }

  wt(dp[0][0]);
}

Current time: 2024年04月24日04時00分26秒
Last modified: 2019年11月10日21時08分24秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF595 CF_Div3_F
トップページに戻る

Logged in as: unknown user (not login)