bzoj4557侦查守卫

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4557

树形DP。和“河流”有点像，也有一个类似“承诺”的东西。

　　就是用 f 表示当前节点向下 j 层之下的需覆盖点已覆盖的费用。答案可以是 f [ root ] [0] 。（root是随便一个点）

　　　　最好把当前节点看作第1层而不是第0层，这样就能用0表示当前节点的子树全覆盖了。

　　为了转移，引入一个 g ，表示当前点在自己子树全覆盖的基础上可以向外覆盖 j 层。这时当前节点可以自然地看作第0层了。

　　　　这也是为什么 f 表示的是“向下 j 层之下的点全覆盖”而不是“向下 j 层全覆盖”。就是为了方便转移。

　　　　　　没错，因为如果记成“向下 j 层全覆盖”，那么记录下“还有一些没覆盖”这一状态也根本没用，因为兄弟节点都是从上往下帮自己覆盖的；

　　　　　　而像这样记录成“向下还有 j 层没覆盖”，就有更多“把它们覆盖好”的机会，也方便转移等等，变得很顺畅！

具体转移的时候，发现 g 的转移依赖 f （上一次的 f 值），而 f 的转移不依赖 g ，所以要先求g的值。

　　可以用g[0]来更新 f [0] 的值，因为f [0] 是从当前节点的孩子们的 f 那里转移不过来的。

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

using namespace std;

const int N=5e5+,D=;const ll INF=0x7fffffff;

int n,m,d,head[N],xnt;

ll a[N],f[N][D],g[N][D];

bool need[N];

struct Edge{

    int next,to;

    Edge(int n=,int t=):next(n),to(t) {}

}edge[N<<];

void add(int a,int b)

{

    edge[++xnt]=Edge(head[a],b);head[a]=xnt;

    edge[++xnt]=Edge(head[b],a);head[b]=xnt;

}

void dfs(int cr,int fa)

{

    f[cr][]=g[cr][]=need[cr]?a[cr]:;//只有根节点时的状态

    for(int j=;j<=d;j++)g[cr][j]=a[cr];//初值

    g[cr][d+]=INF;

    for(int i=head[cr],v;i;i=edge[i].next)

    {

        if((v=edge[i].to)==fa)continue;

        dfs(v,cr);

        for(int j=;j<=d;j++)g[cr][j]=min(g[cr][j]+f[v][j],f[cr][j+]+g[v][j+]);//从0开始

        for(int j=d;j;j--)g[cr][j-]=min(g[cr][j-],g[cr][j]);

        f[cr][]=g[cr][];        //

        for(int j=;j<=d;j++)f[cr][j]+=f[v][j-];        //这个不要放在28行之前，因为该行要用到上一次的值

        for(int j=;j<=d;j++)f[cr][j]=min(f[cr][j],f[cr][j-]);

    }

}

int main()

{

    scanf("%d%d",&n,&d);for(int i=;i<=n;i++)scanf("%lld",&a[i]);

    scanf("%d",&m);int tmp;for(int i=;i<=m;i++){scanf("%d",&tmp);need[tmp]=;}

    int x,y;

    for(int i=;i<n;i++)

    {

        scanf("%d%d",&x,&y);add(x,y);

    }

//    memset(g,1,sizeof g);

    dfs(,);

    printf("%lld",f[][]);

    return ;

}

巴特西

bzoj4557侦查守卫

最新文章

热门文章