Atcoder abc319

發表於 更新於 分類於 ， Disqus： 文章字數： 933 所需閱讀時間 ≈ 3 分鐘
F(dp,bitmask,贪心,bfs)

https://atcoder.jp/contests/abc319

F - Fighter Takahashi

根1,n点 树

非根节点, 2种类型， (si,gi) 或 ((gi) 最多10个)

1
2
3
4
5
6
7
8
初始 s=1 在根
   如果 首次 到点 (ei,si):
       if s < si:
           终止
       else:
          s += gi
   如果 首次 到点 (ei,gi):
          s *= gi

问 能不能经过所有 (si,gi)

n 500

si [1,1e9]

gi [1,1e9]

第二种类型最多10个

2s

1024mb

这不是手机广告里看到的游戏吗 哈哈哈哈哈哈哈

我的思路

这10个，和 n <= 500

我的感觉就是 bitmask乱搞一下？

dp[bitmask] = 恰好把bitmask的 (gi)类型点走完 的最大s

因为所有操作都是增长s的

所以一旦s > max(si)以后，就都可达了

那么对于 (s+w)*v和(s*v+w) 肯定先加会更好

所以步骤是

  1. 当前bitmask,尽量+
  2. 完成加以后走一次 (gi)

尽量+因为和当前s有关系，而办法就是所有可达点找最小的si,因为任何其它顺序的方案，对其 (可达性,si)排序，肯定有等价的 先最小可达si的方案，贪心就完了

那么问题来了，bitmask以后的方案似乎对应的点并不一致

因为在 尽量+的时候走过非bitmask的点

那么还剩下树的性质没有用，如何使用呢？

另一个想法就是 别bitmask了，直接 贪心+10! 吧，反正上面总结的是 每次尽量+，之后才走乘法

所以是

  1. state => 贪心所有可用的+点全部用完
  2. 那么现在剩余有若干个乘法点，这里直接分叉 暴力： $500\cdot 10!=1814400000$个方案

再一个就是两者结合，当达到bitmask且完成尽量+以后，记录s和对应的树状态

因为bitmask完成 和 + 以后，那么树上的不考虑s的 连通点是一样的，在一样的开放连通点情况下

“感觉上是” s越大越优，因为完成了 尽量+

所以 当前两个方案 如果不同 它们s如果相同，那么可达区域 <= s都可达 也就相同

如果它们 s不同，s更大的 可达区域也越大

所以就是 bfs + 贪心 + 优先队列 + bitmask?

直接过了

代码

https://atcoder.jp/contests/abc319/submissions/me

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
const ll INF=1'000'000'000;
ll read(){ll r;scanf("%lld",&r);return r;}
tuple<int,int,int> tsig[510]; // {type,si,gi}, {type,medidx,gi}
vector<int> G[510];
using state = tuple<ll,vector<int>>;
state calc(const state &old){ // 当前状态尽量 找 `+`
  auto [s,tg] = old;
  vector<int> ret;
  set<tuple<int,int,int> > sgu; // 未处理的t==1的点, si, g, u
  auto _=[&](int u){
    auto [t,si,g] = tsig[u];
    if(t == 1) sgu.insert({si,g,u});
    else if(t==2) ret.push_back(u);
  };
  for(auto u:tg) _(u);
  while(sgu.size() and get<0>(*sgu.begin()) <= s) { // 走该点 增大s
    auto [si,g,u] = *sgu.begin();
    sgu.erase(sgu.begin());
    s += g;
    for(auto v:G[u]) _(v);
  }
  for(auto [si,g,u]:sgu) ret.push_back(u); // 剩余未处理的
  return {min(s,INF),ret}; // 注意overflow
}

int main(){
  int medidx = 0; // 药
  int n=read();
  rep(i,2,n+1) {
    int p=read();
    G[p].push_back(i);
    int t=read();
    int si=read();
    int g=read();
    if(t==2) si = medidx++; // {t==2, medicine index, g}
    tsig[i] = {t,si,g};
  }
  // => msk + bfs
  vector<state> best(1<<medidx,{0,{}}); // {s, tinygraph}
  vector<int> tg; // inited tiny graph
  for(auto v:G[1]) tg.push_back(v);
  best[0] = calc({1,tg});

  vector<int> bfs;// mask
  bfs.push_back(0);
  rep(i,0,size(bfs)){
    auto msk = bfs[i];
    const auto &[s,tg] = best[msk];
    rep(j,0,size(tg)) if(get<0>(tsig[tg[j]]) == 2) { // 创建去掉tg[j]的
      int u = tg[j];
      auto [t,medidx,g] = tsig[u];
      vector<int> tmptg;
      rep(k,0,size(tg)) if(j!=k) tmptg.push_back(tg[k]);
      for(auto v:G[u]) tmptg.push_back(v);
      auto [news,newtg] = calc({min(s*g,INF), tmptg}); // 注意overflow
      int newmsk = msk | (1<<medidx);
      auto&[olds,oldtg] = best[newmsk];
      if(olds == 0) bfs.push_back(newmsk);
      if(olds <= news) best[newmsk] = {news,newtg};
    }
  }
  auto &[alls,alltg] = best[(1<<medidx)-1];
  printf("%s\n", (alls>0 and alltg.size() == 0) ? "Yes":"No");
  return 0;
}