[JLOI2016/SHOI2016]侦察守卫（树形dp）

小R和B神正在玩一款游戏。这款游戏的地图由N个点和N-1条无向边组成，每条无向边连接两个点，且地图是连通的。换句话说，游戏的地图是一棵有N个节点的树。

游戏中有一种道具叫做侦查守卫，当一名玩家在一个点上放置侦查守卫后，它可以监视这个点以及与这个点的距离在D以内的所有点。这里两个点之间的距离定义为它们在树上的距离，也就是两个点之间唯一的简单路径上所经过边的条数。在一个点上放置侦查守卫需要付出一定的代价，在不同点放置守卫的代价可能不同。

现在小R知道了所有B神可能会出现的位置，请你计算监视所有这些位置的最小代价。

Solution

神题。

注意到d不是很大，所以可以设计一个NK的状态：dp[i][j]表示i这个点为根的子树已经处理完了，它还能在向上覆盖j个点的最小代价。

但是还有可能会出现子树之间相互覆盖的情况，所以我们用f[i][j]表示以i为根的子树向下还有j个点没有覆盖的最小代价。

转移：

考虑dp数组如何转移。

dp[u][j]<-min(dp[u][j]+f[v][j](u刚好能够向下覆盖j个)，dp[v][j+1]+f[u][j+1]）；

相当于是我们把v合并到了当前子树中。

f数组可以直接累加答案,f[i][j]+=f[v][j-1]。

最后结合一下贪心的思想，对于f数组，j越大答案应越小，对于dp数组，j越小答案也应越小，做完之后取一下min

然后还要注意一下边界，dp[u][0]=0.dp[u][~]=w[u].当vis[u]=1时f[u][0]=dp[u][0]=w[u];

Code

#include<iostream>

#include<cstdio>

#define N 500003

#define inf 0x3f3f3f3f

using namespace std;

int x,y,w[N],head[N],tot,f[N][],d,dp[N][],n,m,tag[N];

struct zzh{

    int n,to;

}e[N<<];

inline void add(int u,int v){

    e[++tot].n=head[u];

    e[tot].to=v;

    head[u]=tot;

}

void dfs(int u,int fa){

    if(tag[u])dp[u][]=f[u][]=w[u];

    for(int i=;i<=d;++i)dp[u][i]=w[u];

    dp[u][d+]=inf;

    for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){

       int v=e[i].to;

       dfs(v,u);

       for(int j=d;j>=;--j)dp[u][j]=min(dp[u][j]+f[v][j],dp[v][j+]+f[u][j+]);

       for(int j=d;j>=;--j)dp[u][j]=min(dp[u][j],dp[u][j+]);

       f[u][]=dp[u][];

       for(int j=;j<=d+;++j)f[u][j]+=f[v][j-];

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

    }

}

inline int rd(){

    int x=;bool f=;char c=getchar();

    while(!isdigit(c)){

        if(c=='-')f=;

        c=getchar();

    }

    while(isdigit(c)){

        x=(x<<)+(x<<)+(c^);

        c=getchar();

    }

    return f?-x:x;

}

int main(){

    n=rd();d=rd();

    for(int i=;i<=n;++i)w[i]=rd();

    m=rd();

    for(int i=;i<=m;++i)x=rd(),tag[x]=;

    for(int i=;i<n;++i)x=rd(),y=rd(),add(x,y),add(y,x);

    dfs(,);

    cout<<f[][];

    return ;

}

巴特西

[JLOI2016/SHOI2016]侦察守卫（树形dp）

最新文章

热门文章