zxyhymzg\color{black}\texttt{z}\color{red}\texttt{xyhymzg} !!!

多年以前的考试小技巧,今天复习一下。

大概应对一类要经过某个点组成联通块的树上背包优化。

一般是做根的一个联通块,若想要做任意点就套上一个淀粉质加一个 log\log 超值加倍。

大概思路是修改 dpudp_u 的含义,本来的含义是在 uu 的子树内做一些事情,现在我们转换为根的一个联通块此时考虑到了 uu 的一些东西。

主要的思路是考虑我们 dpdp 的过程中,是加了一些点到根的联通块中,考虑这些新加点的性质:要不是新加一个点往下走一步,要不直接跳过了这棵子树(由于这一点 dpudp_u 的这个 uu 是还未加入联通块的,此时我们要决策)。

那么这一问题我们有两种解决方式,一种是把 dfndfn 搞出来,此时我们的 dpidp_i 彻底沦为维护原来的 dpidfnidp_{idfn_i} ,那转移就是 dpidpi+1/dpidpi+sizidp_i\to dp_{i+1}/dp_i\to dp_{i+siz_i} 做个刷表背包即可,由于笔者懒得自己写,我们以 20211062021-10-6 T4 为例看,看这一做法。

1
2
3
4
5
6
7
8
9
10
11
dfc = 0; dfs(u,0);
fr(i,1,nds) memset(dp[i],-0x3f,sizeof dp[i]);
dp[1][a[u]] = b[u];
fr(i,2,nds) {
int u = idfn[i];
fr(j,0,m) {
if(j+a[u] <= m) chkmax(dp[i][j+a[u]],dp[i-1][j] + b[u]);
chkmax(dp[i-1+siz[u]][j],dp[i-1][j]);
}
}

是神仙 zxy\texttt{zxy} 的代码,外面还套了一层淀粉质。

这一做法优点是较为好理解,写起了方便不易出锅,除了有个 dfsdfs 小常数为没缺点,平时一定要写这个。

还有一传统做法是我们最初见到路哥优化时使用的,直接在树上做,每次将 dpudp_u 整个数组传给儿子, dfsdfs 后再直接 ckmaxckmax 的做法,同一题中,它是这么写的。

1
2
3
4
5
6
7
8
9
10
11
12
13
void Dp (int u, int fa) {
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (vis[v] || v == fa) continue;
memset (dp[v], 0xcf, sizeof dp[v]);
For (j, a[u], m - a[v]) dp[v][j + a[v]] = dp[u][j] + b[v];
Dp (v, u);
For (j, a[u], m) {
ckmax(dp[u][j], dp[v][j]);
ckmax(Ans, dp[u][j]);
}
}
}

理解的话,这里面水太深,牵扯的人和事太多了不好说,笔者中午没午休,先鸽了。

更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

Odalys 微信支付

微信支付

Odalys 支付宝

支付宝