题解：P2465 [SDOI2008] 山贼集团

注意到

p \leq 12

非常小，考虑状压。设

f_{u, s}

为

u

子树内建立了

s

中的分部的最大答案。转移首先考虑合并子树，有

f'_{u, s \cup t} \gets f_{u, s} + f_{v, t}

直接枚举是

\mathcal{O}(4^p)

的，显然不行，注意到

s, t

必然无交，所以可以枚举

x = s \cup t

，枚举

s

为

x

的子集，就有

t = x \setminus s

，即

f'_{u, x} \gets f_{u, s} + f_{v, x \setminus s}

将复杂度降到了枚举子集的

\mathcal{O}(3^p)

。

合并子树后仅需讨论

u

上建立的分部并加上

u

点的贡献，转移都是简单的。总时间复杂度

\mathcal{O}(n3^p)

。

Code：

CPP

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 100 + 10, maxk = 12;

struct{
    int v, nex;
} edge[maxn << 1];

int n, k, m;
int a[maxn][maxk + 10], b[1 << maxk], f[maxn][1 << maxk], g[1 << maxk];
int head[maxn], top = 0;

inline void add(int u, int v, bool o = true){
    edge[++top].v = v, edge[top].nex = head[u], head[u] = top, o && (add(v, u, false), 1538);
}

inline void dfs(int u, int fa){
    mem(f[u], -0x3f), f[u][0] = 0;
    for (int i = head[u]; i; i = edge[i].nex){
        const int v = edge[i].v;
        if (v != fa){
            dfs(v, u), mem(g, -0x3f);
            for (int sta = 0; sta < 1 << k; sta++){
                for (int st = sta;;st = st - 1 & sta){
                    g[sta] = max(g[sta], f[u][st] + f[v][sta ^ st]);
                    if (!st){
                        break;
                    }
                }
            }
            for (int sta = 0; sta < 1 << k; sta++){
                f[u][sta] = g[sta];
            }
        }
    }
    for (int i = 1; i <= k; i++){
        for (int sta = 0; sta < 1 << k; sta++){
            (sta >> i - 1 & 1) && (f[u][sta] = max(f[u][sta], f[u][sta ^ 1 << i - 1] - a[u][i]));
        }
    }
    for (int sta = 0; sta < 1 << k; sta++){
        for (int st = sta;;st = st - 1 & sta){
            f[u][sta] += b[st];
            if (!st){
                break;
            }
        }
    }
}

int main(){
    scanf("%d %d", &n, &k);
    for (int i = 1; i < n; i++){
        int u, v;
        scanf("%d %d", &u, &v), add(u, v);
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= k; j++){
            scanf("%d", &a[i][j]);
        }
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++){
        int v, k, x = 0;
        scanf("%d %d", &v, &k);
        for (int u; k--; scanf("%d", &u), x |= 1 << u - 1);
        b[x] += v;
    }
    dfs(1, 0);
    printf("%d\n", f[1][(1 << k) - 1]);

return 0;
}

题解：P2465 [SDOI2008] 山贼集团

文章操作

相关推荐

评论

题解：P2465 [SDOI2008] 山贼集团