[JSOI2018]潜入行动
2021-03-28 19:26
标签：problem class 背包 入行 表示 com span 分类 www 传送门 这是树上背包计数？上下界优化裸题？ 考虑大力\(dp\) \(f[u][i][0/1][0/1]\)表示\(u\)子树选了\(i\)个节点，当前点选不选，是否被覆盖 大力分类讨论 \(f[u][i+j][0][0]=\sum f[u][i][0][0]*f[v][j][0][1]\) \(f[u][i+j][0][1]=\sum f[u][i][0][1]*(f[v][j][0][1]+f[v][j][1][1])+f[u][j][0][0]*f[v][j][1][1]\) \(f[u][i+j][1][0]=\sum f[u][i][1][0]*(f[v][j][0][0]+f[v][j][0][1])\) \(f[u][i+j][1][1]=\sum f[u][i][1][0]*(f[v][j][1][0]+f[v][j][1][1])+f[u][i][1][1]*(f[v][j][0][0]+f[v][j][0][1]+f[v][j][1][0]+f[v][j][1][1])\) 虽然很 长长长长长长长长长长长长长长长长长长长长长长长长 但是很显然 我们加一个长得和暴力没多大区别的上下界优化 一道黑题就过了 [JSOI2018]潜入行动 标签：problem class 背包 入行 表示 com span 分类 www 原文地址：https://www.cnblogs.com/knife-rose/p/12617087.html