POI #Year2009 #贪心
贪心的把灭火器放到深度较小的点上,对于每个点,维护两个数组,记录距离当前点为 \(x\) 没有覆盖的点有 \(a_x\)个,距离当前点\(y\) 的灭火器有 \(b_y\) 个
然后在每个点上,合并长度为 \(len\) 或者 \(len-1\) 的路径,因为这些路径不能延伸到父节点,所以要在这个点解决
如果当前点的 \(a_{len}>0\) 那么考虑在当前点放灭火器覆盖这些点,然后更新 \(b\)
注意特判在 \(1\) 上时要将所有可以的全部覆盖上,而不限制覆盖的长度
// Author: xiaruize
const int N = 1e5 + 10;
int n, s, k;
vector<int> g[N];
int cnt[N][25], rm[N][25];
int res = 0;
void dfs(int x, int fa)
{
cnt[x][0]++;
for (auto v : g[x])
{
if (v == fa)
continue;
dfs(v, x);
rep(i, 0, k - 1)
{
cnt[x][i + 1] += cnt[v][i];
rm[x][i + 1] += rm[v][i];
}
}
per(i, k, 0)
{
per(j, k - i, max(0, k - i - 1))
{
int tmp = min(cnt[x][i], rm[x][j]);
cnt[x][i] -= tmp;
rm[x][j] -= tmp;
}
}
if (cnt[x][k])
{
int tmp = (cnt[x][k] + s - 1) / s;
rm[x][0] += tmp * s;
res += tmp;
}
per(i, k, 0)
{
per(j, k - i, max(0, k - i - 1))
{
int tmp = min(cnt[x][i], rm[x][j]);
cnt[x][i] -= tmp;
rm[x][j] -= tmp;
}
}
// debug(x, res, cnt[x], rm[x]);
}
void solve()
{
cin >> n >> s >> k;
rep(i, 1, n - 1)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
int x = 1;
per(i, k, 0)
{
per(j, k - i, 0)
{
int tmp = min(cnt[x][i], rm[x][j]);
cnt[x][i] -= tmp;
rm[x][j] -= tmp;
}
}
int tmp = 0;
rep(i, 0, k) tmp += cnt[1][i];
cout << res + (tmp + s - 1) / s << endl;
}
#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
#ifndef ONLINE_JUDGE
cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
return 0;
}
标签:tmp,cnt,Fire,per,int,dfs,rm,POI2009GAS,Extinguishers
From: https://www.cnblogs.com/xiaruize/p/18142216