众所周知,正确写法的树形背包在第二维是 O(c) 的情况下复杂度是 O(nc) 的。但是如果上下界不精细就会写成 O(nc2)。
例如
for(int i = 0; i <= c; i++)
for(int j = 0; j <= siz[y]; j++)
for(int i = 0; i <= siz[x]; i++)
for(int j = 0; j <= c; j++)
for(int i = 0; i <= siz[x] + siz[y]; i++)
for(int j = 0; j <= siz[x]; j++)
for(int i = 0; i <= c; i++)
for(int j = 0; j <= siz[x] + siz[y] - i; j++)
...
如何卡这种写错的树形背包?有一种通用的卡法吗?