Luogu P3177 [HAOI 2015] 树上染色

题目链接: https://www.luogu.com.cn/problem/P3177

0 说在之前

树形 DP 要么模板题,要么神仙题

这个题就属于不太正常的

1 思路

$f_{i,j}$

其中 $i$ 代表当前节点

$j$ 代表子树中选择 $j$ 个黑点,所能对答案产生的贡献

有了这个思路,后面的东西就是标准的树上背包了

2 Code

#include <cstdio>
#include <cstring>

inline int Min(int a, int b) { return a < b? a : b; }
inline long long Max(long long a, long long b) { return a > b? a : b; }

const int N = 2100;

int n, m;
int size[N];

// Edge Start
struct edge {
    int to, val, next;
} e[N << 1];
int ehead[N], ecnt;

inline void add_edge(int now, int to, int val) {
    ecnt ++;
    e[ecnt].to = to;
    e[ecnt].val = val;
    e[ecnt].next = ehead[now];
    ehead[now] = ecnt;
}
// Edge End

// DP Start
long long f[N][N];
void dp(int now, int la) {
    size[now] = 1;
    f[now][0] = f[now][1] = 0;
    for(int i = ehead[now]; i; i = e[i].next) {
        if( e[i].to == la )
            continue;
        dp(e[i].to, now);
        size[now] += size[ e[i].to ];
        for(int j = Min(size[now], m); j >= 0; j--) {
            for(int k = 0; k <= Min(size[ e[i].to ], j); k++) {
                if( f[now][ j - k ] == -1 )
                    continue;
                long long val = 1LL * ( 1LL * k * ( m - k ) + 1LL * ( size[ e[i].to ] - k ) * ( n - m - size[ e[i].to ] + k ) ) * e[i].val;
                f[now][j] = Max( f[now][j], f[now][j - k] + f[ e[i].to ][k] + val);
            }
        }
    }
}
// DP End

int main() {
#ifdef woshiluo
    freopen("luogu.3177.in", "r", stdin);
    freopen("luogu.3177.out", "w", stdout);
#endif
    scanf("%d%d", &n, &m);
    for(int i = 1, u, v, w; i < n; i++) {
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }

    memset(f, -1, sizeof(f));
    dp(1, 0);

    printf("%lld", f[1][m]);
    fclose(stdin);
    fclose(stdout);
}

Luogu P2607 [ZJOI2008]骑士

题目链接: https://www.luogu.org/problemnew/show/P2607

题目意思非常简单,给你一张图,然后图中不能选最大相邻点,最后最大的选中的点的权值

很容易想到 没有上司的舞会 这种树形 DP 题目,但是显然,这,并不是一棵树

根据题目可得,每一个人只会有一条出边,即,这张图中,一张节点个数为 $n$ 的联通块,会有 $n$ 条边

环套树没得跑了

即每一个联通块中一定有一条边,删掉后就是树了

设这条边为 $u – v$ 的边,则 $\max(f_{u,0}, f_{u,1})$ 就是这个联通块的答案

建双向边判环即可

至于代码中的 xor ,当反向边即可

Continue reading “Luogu P2607 [ZJOI2008]骑士”

Luogu P3174 [HAOI2009]毛毛虫

题目链接: https://www.luogu.org/problemnew/show/P3174

这应该是我第一次没看 sol 做紫题吧……

虽然个人感觉比大多数紫题简单许多

题目本质是要求最长链的,但是要求是带每个点周围点的

我们设每个点的点权是这个点的连接点个数减 1

然后求最长链

得出来的链的长度 +2 即为答案

可以理解为因为大多数点都有一条边要连出去防止重复计算而减一

但是这样链头链尾会没算上,所以加二

Continue reading “Luogu P3174 [HAOI2009]毛毛虫”