做网站是不是要有数据库,苏州seo报价,网站建设知识库,网站开发公司名称https://www.lydsy.com/JudgeOnline/problem.php?id4557 小R和B神正在玩一款游戏。这款游戏的地图由N个点和N-1条无向边组成#xff0c;每条无向边连接两个点#xff0c;且地图是连通的。换句话说#xff0c;游戏的地图是一棵有N个节点的树。 游戏中有一种道具叫做侦查守卫…https://www.lydsy.com/JudgeOnline/problem.php?id4557 小R和B神正在玩一款游戏。这款游戏的地图由N个点和N-1条无向边组成每条无向边连接两个点且地图是连通的。换句话说游戏的地图是一棵有N个节点的树。 游戏中有一种道具叫做侦查守卫当一名玩家在一个点上放置侦查守卫后它可以监视这个点以及与这个点的距离在D以内的所有点。这里两个点之间的距离定义为它们在树上的距离也就是两个点之间唯一的简单路径上所经过边的条数。在一个点上放置侦查守卫需要付出一定的代价在不同点放置守卫的代价可能不同。 现在小R知道了所有B神可能会出现的位置请你计算监视所有这些位置的最小代价。 dp状态很好想但是这个式子我菜我是真的推不出来其他的巨佬切题的速度叹为观止只能感叹我的智商摆在这里。 参考https://www.luogu.org/blog/zcysky/solution-p3267 一眼是个树形dp二眼$d$很小可以直接做成一维状态那么直接设$f[i][j]$为$i$子树从$i$往下$j$层都没有覆盖的代价$g[i][j]$为$i$的子树全覆盖往上还可以覆盖$j$层的代价。二者正好是互补的。 PS层数也包括i本身换句话说$j0$时$i$并没有被覆盖我在这里纠结了很久。 PPS既然$g[i][j]$都可以覆盖上$j$层那它也能覆盖下$j$层。 之后对于dp式子慢慢剖析因为我自己都云里雾里的。 边界就是当点$u$为关键点时$f[u][0]g[u][0]w[u]$这个点一定是要放一个的如果不是的话显然我们就不需要放了初值为0。 初始化就不说了。 对于每个儿子结点v我们有 $g[u][j]min(g[u][j]f[v][j],g[v][j1]f[u][j1])$所以明白f和g是互补的才能看懂 当然也有可能出现这种的$g[u][j]min(g[u][j],g[u][j1])$ 推完g来推f首先$f[u][0]g[u][0]$因为此时二者状态等价。 然后显然的$f[u][j]f[v][j-1]$ 以及也有可能出现这种的$f[u][j]min(f[u][j],f[u][j-1])$ 所以其实核心还是在状态含义上而非式子含义搞懂式子就很显然了。 #includemap
#includecmath
#includestack
#includequeue
#includecstdio
#includecctype
#includevector
#includecstdlib
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const int N5e55;
const int D21;
const int INF1e9;
inline int read(){int X0,w0;char ch0;while(!isdigit(ch)){w|ch-;chgetchar();}while(isdigit(ch))X(X3)(X1)(ch^48),chgetchar();return w?-X:X;
}
struct node{int to,nxt;
}e[N*2];
int n,d,m,cnt,head[N],w[N];
int f[N][D],g[N][D];
bool im[N];
inline void add(int u,int v){e[cnt].tov;e[cnt].nxthead[u];head[u]cnt;
}
void dfs(int u,int fa){if(im[u])f[u][0]g[u][0]w[u];for(int i1;id;i)g[u][i]w[u];g[u][d1]INF;for(int ihead[u];i;ie[i].nxt){int ve[i].to;if(vfa)continue;dfs(v,u);for(int jd;j0;j--)g[u][j]min(g[u][j]f[v][j],g[v][j1]f[u][j1]);for(int jd;j0;j--)g[u][j]min(g[u][j],g[u][j1]);f[u][0]g[u][0];for(int j1;jd1;j)f[u][j]f[v][j-1];for(int j1;jd1;j)f[u][j]min(f[u][j],f[u][j-1]);}
}
int main(){nread(),dread();for(int i1;in;i)w[i]read();mread();for(int i1;im;i)im[read()]1;for(int i1;in;i){int uread(),vread();add(u,v);add(v,u);}dfs(1,0);printf(%d\n,f[1][0]);return 0;
} 本文作者luyouqi233。 欢迎访问我的博客http://www.cnblogs.com/luyouqi233/ 转载于:https://www.cnblogs.com/luyouqi233/p/9193761.html
