‹ 上一题 下一题 ›

g6-07557. max 型与 min 型·骨架相同初值不同 未做

1000 ms 256 MB 测试点 ? 通过率 50% 自拟题知识点题GESP-66级·树形 DP 入门客观题单选

最大权独立集是 max 型(求收益最大),路径覆盖最小代价是 min 型(求代价最小)。两者的状态骨架几乎一样,但有一个关键差别,它是( )。

  • A. max 型初值取 (什么都不选也是合法方案),min 型初值取 (不可行必须用大数占位)——否则 min 型会把「不合法」当成 0 代价,得到错误答案
  • B. 两者只差一个把 换成 ,初值无所谓
  • C. min 型不能用树形 DP,只能枚举
  • D. max 型的答案是 ,min 型必须输出全局最小值
未选择
输入
输出

            
答案