ABC341F

問題

ABC341F

解法

駒を一つ固定して考える．
無向グラフと書かれているが，コストが真に小さい vertex に駒を(必要なら増やした上で)移動するので，
有限回で終わるかつ有向グラフとみなしてよい．

$dp_{v}$ を，頂点 $v$ に駒があるときに最大で移動できる回数，と定義する．
式で表せば

$$dp_{v} := 1 + \displaystyle \max_{S} \sum_{u \in S} dp_{u}$$

と書ける．$S$ は $\{ S \in 2^{to_{v}} \ \vert\ \sum_{u \in S} W_{u} \in W_{v}\}$ 全体を動く．

つまり，$dp_{v}$ の 2項目は，

• コストを $W_{u}$，
• 価値を $dp_{u}$
  とするナップザック問題を解けば求まる．

$W_{v}$ が小さい順に調べるので，頂点全体を $W$ の昇順にソートしておく．
このとき，頂点全体をソートしておけば十分．
$W_{v}$ などを一緒にソートするのは不要．

コード

main.cpp

int main() {
  ll n,m;
  cin >> n >> m;
  vvll to(n);
  rep(i,m){
    ll a,b; cin >> a >> b;
    --a, --b;
    to[a].emplace_back(b);
    to[b].emplace_back(a);
  }

  vll w(n), a(n);
  cinv(w); cinv(a);

  vll vs(n); rep(i,n) vs[i] = i;
  sort(all(vs), [=](ll i, ll j){ return w[i] < w[j]; });

  vll dp(n);
  for(auto v: vs){ // rem: for の内部で dp[u] (u < v in vs) を用いている事を確認
    // max_val を Knapsack problem を解いて求める．
    //   cost(u) = w[u], 
    //   value(u) = dp[u]  
    
    vll knapsack_cost_to_val(w[v]);
    for(auto u: to[v]) if(w[u] < w[v]){
      drep(cost, w[v]){ // w[v] 未満しか使わない
        if(cost - w[u] < 0) break;
        chmax(knapsack_cost_to_val[cost], knapsack_cost_to_val[cost - w[u]] + dp[u]);
      }
    }
    
    ll max_val = 0;
    rep(cost, w[v]) chmax(max_val, knapsack_cost_to_val[cost]);

    chmax(dp[v], max_val + 1); 
  }

  ll ans = 0;
  rep(v,n) ans += a[v] * dp[v];
  cout << ans << endl;

  return 0;
}