P1273 有线电视网
树上背包的变形
\[f_{u, j + k} = \max_{v \in son(u)} f_{u, j} + f_{v, k} - w_{u,v} \]这里写成 \(j + k\) 是为了和代码一致。
\(f_{u,j + k}\) 代表以 \(u\) 为根的子树中,选择了 \(j + k\) 个叶子结点的利润最大值。
\(w_{u, v}\) 代表 \(u\) 到 \(v\) 的边权。
然后就是很朴素的树上背包了,注意维护的是利润的最大值,有负数出现,需要初始化一下,详细见代码。
int n, m, w[N];
int sz[N], f[N][N], tmp[N], dep[N];
vector<pair<int, int>> e[N];
void dfs(int u)
{
if(u >= n - m + 1)
{
f[u][1] = w[u];
sz[u] = 1;
return;
}
sz[u] = 0;
for(auto [v, w] : e[u])
{
dfs(v);
for(int i = 0; i <= sz[u] + sz[v]; i++)
tmp[i] = f[u][i];
for(int i = 0; i <= sz[u]; i++)
for(int j = 0; j <= sz[v]; j++)
tmp[i + j] = max(tmp[i + j], f[u][i] + f[v][j] - w);
sz[u] += sz[v];
for(int i = sz[u]; i >= 0; i--)
f[u][i] = tmp[i];
// for(int i = sz[u]; i >= 0; i--)
// {
// cout<<"U: "<<u<<" V: "<<v<<" sz[u]: "<<i<<" f_u_sz: "<<f[u][i]<<'\n';
// }
}
}
void solve()
{
cin>>n>>m;
for(int i = 1; i <= n - m; i++)
{
int k; cin>>k;
for(int j = 1; j <= k; j++)
{
int v, k; cin>>v>>k;
e[i].push_back({v, k});
}
}
for(int i = n - m + 1; i <= n; i++)
cin>>w[i];
for(int i = 1; i <= n; i++)
{
f[i][0] = 0;
for(int j = 1; j <= n; j++)
f[i][j] = -inf;
}
dfs(1);
for(int i = m; i >= 0; i--)
{
if(f[1][i] >= 0)
{
cout<<i<<'\n';
return;
}
}
return;
}
P2279 [HNOI2003] 消防局的设立
类似题目P2899 [USACO08JAN] Cell Phone Network G,不同处在于只覆盖相邻的
设 \(f_{u, i}\) 为以u为根的子树,消防局可以覆盖的范围,其中 \(i \in [0, 4]\),分别代表可以覆盖到 \(dep_u + 2\), \(dep_u + 1\), \(dep_u\),\(dep_u - 1\),\(dep_u - 2\)层。
有转移方程
\[f_{u, 0} = 1 + \sum_{v \in son(u)} f_{v, 4} \\ f_{u, 1} = \sum_{v \in son(u)} f_{v, 3} - \max_{v \in son(u)} (f_{v,3} - f_{v, 0}) \\ f_{u, 2} = \sum_{v \in son(u)} f_{v, 2} - \max_{v \in son(u)} (f_{v, 2} - f_{v, 1}) \\ f_{u, 3} = \sum_{v \in son(u)} f_{v, 2} \\ f_{u, 4} = \sum_{v \in son(u)} f_{v, 3} \\ \]注意!还需要在dp中对最小值进行转移
for(int i = 1; i <= 4; i++) f[u][i] = min(f[u][i - 1], f[u][i]);
int n;
int dep[N], f[N][10];
vector<int> e[N];
void dfs(int u, int from)
{
f[u][0] = 1;
f[u][1] = f[u][2] = 1e8;
int s1 = 0, s2 = 0;
for(auto v : e[u])
{
if(v == from) continue;
dfs(v, u);
f[u][0] = f[u][0] + f[v][4];
s1 = s1 + f[v][3];
s2 = s2 + f[v][2];
f[u][3] = f[u][3] + f[v][2];
f[u][4] = f[u][4] + f[v][3];
}
for(auto v : e[u])
{
if(v == from) continue;
f[u][1] = min(s1 - f[v][3] + f[v][0], f[u][1]);
f[u][2] = min(s2 - f[v][2] + f[v][1], f[u][2]);
}
for(int i = 1; i <= 4; i++) f[u][i] = min(f[u][i - 1], f[u][i]);
}
void solve()
{
cin>>n;
for(int v = 2; v <= n; v++)
{
int u; cin>>u;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
cout<<min({f[1][0], f[1][1], f[1][2]})<<'\n';
return;
}
P5662 [CSP-J2019] 纪念品
只要领悟到当天买的可以当天卖,求出今天买明天卖的最大值,就很简单了
int t, n, m, a[110][110], res;
int f[N];
void solve()
{
cin>>t>>n>>m;
for(int i = 1; i <= t; i++)
for(int j = 1; j <= n; j++)
cin>>a[i][j];
for(int k = 1; k < t; k++)
{
memset(f, 0, sizeof f);
for(int i = 1; i <= n; i++)
{
for(int j = a[k][i]; j <= m; j++)
f[j] = max(f[j], f[j - a[k][i]] - a[k][i] + a[k + 1][i]);
}
m = max(f[m] + m, m);
}
cout<<m<<'\n';
return;
}
后面蓝色大部分都是分组背包+完全背包的题
CF219 Choosing Capital for Treeland
换根dp
\(1\) 为根结点, \(f_u\) 为以 \(u\) 为根的子树不需要反转的道路数量
\(g_v\) 为以 \(v\) 为整棵树的根结点,在以 \(1\) 为整棵树的根结点下 \(v\) 的父亲 \(u\) 的子树不需要反转的道路数量
有点绕,不知道意思清不清晰
f[u] = f[u] + f[v];
if(S.count({u, v})) f[u]++;
g[v] = g[u] + f[u] - f[v] + (S.count({v, u}) ? 1 : -1);
ll n, f[N], g[N];
vector<int> e[N];
set<pair<int, int>> S;
void dfs(int u, int from)
{
for(auto v : e[u])
{
if(v == from) continue;
dfs(v, u);
f[u] = f[u] + f[v];
if(S.count({u, v})) f[u]++;
}
}
void dfs2(int u, int from)
{
for(auto v : e[u])
{
if(v == from) continue;
g[v] = g[u] + f[u] - f[v] + (S.count({v, u}) ? 1 : -1);
dfs2(v, u);
}
}
void solve()
{
cin>>n;
for(int i = 1; i < n; i++)
{
int u, v; cin>>u>>v;
S.insert({u, v});
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
dfs2(1, 0);
int miv = -1;
vector<int> res;
for(int u = 1; u <= n; u++)
{
if(f[u] + g[u] > miv)
{
miv = f[u] + g[u];
res.clear();
}
if(f[u] + g[u] == miv)
res.push_back(u);
}
cout<<n - miv - 1<<'\n';
for(auto u : res)
cout<<u<<' ';
cout<<'\n';
return;
}
CF767C Garland
\(sum = \sum _ {i = 1} ^ {n} a_i\)
\(f_u = a_u + \sum _ {v \in son(u)} f_v\)
直接dfs判断是否有 \(f_u = sum / 3\)
注意特判 \(u\) 的次数可以出现超过2次,因为有负数点权,记得把子树情况,和 sum % 3 != 0
的特判
int n, f[N], w[N];
vector<int> e[N];
bool ok = true;
int res[N], cnt, sum;
void dfs(int u, int from)
{
f[u] = w[u];
for(auto v : e[u])
{
if(v == from) continue;
dfs(v, u);
f[u] = f[u] + f[v];
}
if(f[u] == sum / 3)
{
f[u] = 0;
res[++cnt] = u;
}
//f[u] = w[u];
}
void solve()
{
cin>>n;
int root = 0;
for(int i = 1; i <= n; i++)
{
int u; cin>>u>>w[i];
if(u == 0) root = i;
else e[u].push_back(i);
sum += w[i];
}
//cout<<root<<'\n';
dfs(root, 0);
if(sum % 3 != 0 || cnt <= 2)
{
cout<<-1<<'\n';
return;
}
cout<<res[1]<<" "<<res[2]<<'\n';
return;
}
ZJOI2007] 时态同步
深度小的增长到深度大的
\(f_u = \max_{v \in son(u)} f_v + w\)
\(res = \sum _ {u = 1} ^ {n} \sum _ {v \in son(u)} f_u - f_v - w\)
\(w\) 为 \(u\) 和 \(v\) 之间的边权
int n;
ll dep[N], f[N];
vector<pair<int, int>> e[N];
ll res;
void dfs(int u, int from)
{
for(auto [v, w] : e[u])
{
if(v == from) continue;
dfs(v, u);
f[u] = max(f[u], f[v] + w);
}
for(auto [v, w] : e[u])
{
if(v == from) continue;
res += (f[u] - f[v] - w);
}
}
void solve()
{
cin>>n;
int s; cin>>s;
for(int i = 1; i < n; i++)
{
int u, v, w; cin>>u>>v>>w;
e[u].push_back({v, w});
e[v].push_back({u, w});
}
dfs(s, 0);
cout<<res<<'\n';
return;
}
P2279 [HNOI2003] 消防局的设立
不是最大独立集
1 个点可以覆盖其爷爷,父亲,自己,也可以被儿子,孙子覆盖
考虑各个点之间的覆盖转移
注意转移最小值
int n;
int dep[N], f[N][10];
vector<int> e[N];
void dfs(int u, int from)
{
f[u][0] = 1;
f[u][1] = f[u][2] = 1e8;
int s1 = 0, s2 = 0;
for(auto v : e[u])
{
if(v == from) continue;
dfs(v, u);
f[u][0] = f[u][0] + f[v][4];
s1 = s1 + f[v][3];
s2 = s2 + f[v][2];
f[u][3] = f[u][3] + f[v][2];
f[u][4] = f[u][4] + f[v][3];
}
for(auto v : e[u])
{
if(v == from) continue;
f[u][1] = min(s1 - f[v][3] + f[v][0], f[u][1]);
f[u][2] = min(s2 - f[v][2] + f[v][1], f[u][2]);
}
for(int i = 1; i <= 4; i++) f[u][i] = min(f[u][i - 1], f[u][i]);
}
void solve()
{
cin>>n;
for(int v = 2; v <= n; v++)
{
int u; cin>>u;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
cout<<min({f[1][0], f[1][1], f[1][2]})<<'\n';
return;
}
P2899 [USACO08JAN] Cell Phone Network G
思路同上题
P2986 [USACO10MAR] Great Cow Gathering G
换根dp
int n;
ll m,c[N], f[N], g[N], sz[N];
vector<pll> e[N];
void dfs1(int u,int fa)
{
for(auto v : e[u])
{
if(v.fi == fa) continue;
dfs1(v.fi, u);
sz[u] += sz[v.fi];
f[u] += f[v.fi] + sz[v.fi] * v.se;
}
sz[u] += c[u];
}
void dfs2(int u,int fa)
{
for(auto v : e[u])
{
if(v.fi == fa) continue;
g[v.fi] = g[u] + f[u] - f[v.fi] - sz[v.fi] * v.se + (m - sz[v.fi]) * v.se;
dfs2(v.fi, u);
}
}
void solve()
{
cin>>n;
for(int i = 1; i <= n; i++)
{
cin>>c[i];
m += c[i];
}
for(int i = 1; i < n; i++)
{
ll u, v, w; cin>>u>>v>>w;
e[u].pb({v, w});
e[v].pb({u, w});
}
dfs1(1, 0);
dfs2(1, 0);
ll ans = 1e18;
for(int i = 1; i <= n; i++)
ans = min(ans, f[i] + g[i]);
cout<<ans<<endl;
return;
}
P2585 [ZJOI2006] 三色二叉树
树形dp
我喜欢把树建出来再做
int n;
int f[N][4], g[N][4];
// R G B
vector<int> e[N];
string s;
int cnt = 1;
int k = 0;
void build(int u)
{
if(s[k] == '2')
{
int l = ++cnt, r = ++cnt;
e[u].push_back(l);
e[u].push_back(r);
k++;
build(l);
build(r);
}
else if(s[k] == '1')
{
int l = ++cnt;
e[u].push_back(l);
k++;
build(l);
}
else if(s[k] == '0')
k++;
}
void dfs(int u, int from)
{
for(auto v : e[u])
{
if(v == from) continue;
dfs(v, u);
}
if(e[u].size() == 2)
{
int v1 = e[u][0], v2 = e[u][1];
f[u][1] = max({f[v1][2] + f[v2][3], f[v1][3] + f[v2][2]});
f[u][2] = max({f[v1][1] + f[v2][3], f[v1][3] + f[v2][1]}) + 1;
f[u][3] = max({f[v1][1] + f[v2][2], f[v1][2] + f[v2][1]});
g[u][1] = min({g[v1][2] + g[v2][3], g[v1][3] + g[v2][2]});
g[u][2] = min({g[v1][1] + g[v2][3], g[v1][3] + g[v2][1]}) + 1;
g[u][3] = min({g[v1][1] + g[v2][2], g[v1][2] + g[v2][1]});
}
else if(e[u].size() == 1)
{
int v = e[u][0];
f[u][1] = max(f[v][2], f[v][3]);
f[u][2] = max(f[v][1], f[v][3]) + 1;
f[u][3] = max(f[v][1], f[v][2]);
g[u][1] = min(g[v][2], g[v][3]);
g[u][2] = min(g[v][1], g[v][3]) + 1;
g[u][3] = min(g[v][1], g[v][2]);
}
else
{
f[u][2] = g[u][2] = 1;
}
}
void solve()
{
cin>>s;
build(1);
n = cnt;
dfs(1, 0);
cout<<max({f[1][1], f[1][2], f[1][3]})<<" "<<min({g[1][1], g[1][2], g[1][3]})<<'\n';
return;
}
P1272 重建道路
我的dp记录删除多少个点的最小代价,故复杂度是\(O(N^2)\)
int n, k;
vector<int> e[N];
int sz[N], f[N][N], tmp[N];
void dfs(int u, int from)
{
f[u][0] = sz[u] = 0;
for(auto v : e[u])
{
if(v == from) continue;
dfs(v, u);
for(int i = 1; i <= sz[u] + sz[v]; i++)
tmp[i] = inf;
for(int i = 0; i <= sz[u]; i++)
{
for(int j = 0; j < sz[v]; j++)
tmp[i + j] = min(tmp[i + j], f[u][i] + f[v][j]);
tmp[i + sz[v]] = min(tmp[i + sz[v]], f[u][i] + 1);
}
sz[u] += sz[v];
for(int i = sz[u]; i >= 0; i--)
f[u][i] = tmp[i];
}
sz[u]++;
}
void solve()
{
cin>>n>>k;
for(int i = 1; i < n; i++)
{
int u, v; cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
int res = f[1][n - k];
for(int i = 2; i <= n; i++)
if(sz[i] >= k)
res = min(f[i][sz[i] - k] + 1, res);
cout<<res<<'\n';
return;
}
P3177 [HAOI2015] 树上染色
一条边经过次数是 \(times = j \times (k - j) + (sz_v - j) \times (n - k + j - sz_v)\)
\(j\) 是子树的黑节点, \(sz_v\) 是子树的结点数量
const int N = 2e3 + 10;
const ll inf = 1ll << 60;
int n, k;
ll sz[N], w[N], f[N][N], tmp[N];
vector<pair<ll, ll>> e[N];
void dfs(int u, int from)
{
f[u][0] = f[u][1] = 0;
sz[u] = 1;
for(auto [v, w] : e[u])
{
if(v == from) continue;
dfs(v, u);
for(int i = 0; i <= sz[u] + sz[v]; i++)
tmp[i] = -inf;
for(int i = 0; i <= sz[u]; i++)
for(int j = 0; j <= sz[v]; j++)
{
ll times = j * (k - j) + (sz[v] - j) * (n - k + j - sz[v]);
tmp[i + j] = max(tmp[i + j], f[u][i] + f[v][j] + times * w);
}
sz[u] += sz[v];
for(int i = sz[u]; i >= 0; i--)
f[u][i] = tmp[i];
}
}
void solve()
{
cin>>n>>k;
for(int i = 2; i <= n; i++)
{
int u, v, w; cin>>u>>v>>w;
e[u].push_back({v, w});
e[v].push_back({u, w});
}
dfs(1, 0);
cout<<f[1][k]<<'\n';
return;
}
标签:sz,int,void,back,dfs,push,一些,DP
From: https://www.cnblogs.com/magicat/p/17611545.html