BZOJ 1217: [HNOI2003]消防局的设立

//尽管是水题也还是写到博客上吧。。。谁叫我太弱。。。难题都不会

Solution:

第一感觉树形dp 仔细看一下 好像贪心可做…但不是很会 仔细思考google后发现确实可做
显然设立消防局最优策略就是每4个位置设立一个
我们可以直接dfs 给每个点记录一个 f[i] 表示这个点与最近的消防局的距离,显然当 f[i] == 5的时候我们就需要设立一个即 ++ ans 且 f[i] = 0 即可
每个点的 f[i] 需要判断它的子节点的消防局范围是否可以互相覆盖 如果行用mn + 1即可 否则mx + 1即可
还需要注意如果是叶子节点需要在两个位置以内设立消防局 所以叶子节点的f[i]给3就好了
根节点特判3以下即可
//参考这篇博客

Code:

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1001;
const int INF = 10001;
int n, ans, ce, f[N];
int head[N], nex[N << 1], to[N << 1];
inline void add(int u, int v) {
    to[++ ce] = v; nex[ce] = head[u]; head[u] = ce;
    to[++ ce] = u; nex[ce] = head[v]; head[v] = ce;
}
inline void dfs(int x, int fa) {
    int mx = -INF, mn = INF;
    for(int i = head[x]; i != -1; i = nex[i]) {
        int v = to[i];
        if(v == fa) continue;
        dfs(v, x);
        mx = mx > f[v] ? mx : f[v];
        mn = mn < f[v] ? mn : f[v];
    }
    f[x] = mx + mn <= 3 ? mn + 1 : mx + 1;
    if(mn == INF) f[x] = 3;
    if(f[x] == 5) ++ ans, f[x] = 0;
    else if(f[x] >= 3 && fa == -23) ++ ans; 
}
inline int read() {
    int x = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') w = 1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return w ? - x : x;
}
int main() {
    memset(head, -1, sizeof head);
    n = read();
    for(int i = 2; i <= n; ++ i)
        add(i, read());
    dfs(1, -23);
    printf("%d", ans);
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注