求助,统计DAG个数怎么一层层加点dp啊?
  • 板块学术版
  • 楼主wuhao2005
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/8/9 18:16
  • 上次更新2023/11/4 11:24:23
查看原帖
求助,统计DAG个数怎么一层层加点dp啊?
81274
wuhao2005楼主2021/8/9 18:16

就是这道题CF1466H 第二篇题解中说的

对于这种求DAG方案数的DP,往往可以考虑一层一层的加点。假设 dpi,jdp_{i,j} 表示现在图中已加入 ii 个点,上一层有 jj个点的方案数(要带上 ff 的贡献),那么:

这个 dpdp 该怎么弄啊?

不是说多项式的那种,这题要维护其它信息虽然年我也不会

2021/8/9 18:16
加载中...