Ray.C.L

题解

/ 注册

全部文章 / 题解（共32篇）

黑白树

思路：从子节点染色然到父节点，我们看每个节点的覆盖长度还有他子节点的覆盖长度，如果他的覆盖长度dep[u]>dp[v]-1他子节点的覆盖长度那么我们就去用大的更新dep[u]=max(dep[u],dep[v]-1)然后我们记录一下当覆盖距离为0时，他就只能靠自己去覆盖 #include &l...

2020-08-17

0 864

旅游

思路：问能住几个晚上，每个晚上住的地方都是不相邻的，最大独立集问题。dp[i][0/1]表示以i为根节点并且不选/选这个点的最大值。如题i节点如果选了那么下个节点必定不能选如果i不选那么子节点可选可不选 #include <cstdio> #include <cstring>...

2020-08-17

0 710

树上子链

思路：dp[i]表示以i为根节点的子链最大值是多少，u为根时，v为u的子节点，我们可以让u和v两条链相连可得，res=max(res,dp[u]+dp[v])，在dfs的时候不断合并两条链取最大值，然后我们再更新此时u这条链，dp[u]=max(dp[u]，a[u]+dp[v])，因为可能全为负数所...

2020-08-11

0 896

二叉苹果树

思路：题中说明这是标准的二叉树，给我们q个枝那说明连了q+1的点，我们就可以吧边的权值用节点去存，用dp[i][j]表示以i为根节点，连了共j个节点的最大值，因为每个节点只有2个或0个子节点，那么我们枚举2个子节点可能连接的节点数，我们先dfs一次去求出每个节点的2个子节点分别是谁，并在此时给节点附...

2020-08-11

0 690

Cell Phone Network（最小支配集）

思路：要选最少的点去覆盖完整个树，根据覆盖关系我们有3个状态。 1.dp[i][0]表示以i为根节点，选i覆盖完所有子树的最小值 2.dp[i][1]表示不选i，i节点被子节点覆盖 3.dp[i][2]表示不选i节点，i节点被父亲节点覆盖。对于第一种状态，i选以后他的子节点的覆盖关系就是3种取最小...

2020-08-10

0 956

排座椅

思路：行和列怎么划分相互没有干扰，分开算，根据给的坐标我们去算那个位置接耳的人多我们去吧他们分开，存一下位置，最后答案要对位置从小到大输出。 #include <cstdio> #include <cstring> #include <algorithm> #in...

2020-08-10

1 864

poj1463 NC106060 Strategic game（树形DP,树的最小覆盖点）

题意：一城堡的所有的道路形成一个n个节点的树，如果在一个节点上放上一个士兵，那么和这个节点相连的边就会被看守住，问把所有边看守住最少需要放多少士兵。思路：用dp[i][0]表示以i为根节点，但是i节点不放士兵需要看守的最少士兵是多少,dp[i][1]表示以i为根节点，i节点放置守卫时所需的最少...

2020-08-10

0 1143

没有上司的舞会

思路：dp[i][0]就表示以i节点为根节点，不选i节点的最大值，dp[i][1]表示以i节点为根节点，选择i节点的最大值，我们建好图，然后v为u的子节点，当u节点不选的时候，那么后面v节点选和不选我们找一个最大值dp[u][0]+=max(dp[v][0],dp[v][1])。当u节点选的时候那么...

2020-08-09

0 619

小G有一棵大树

思路：找平衡点，删掉一个点后子树节点差最小的就是平衡点，size[i]表示以i节点给根的子节点的个数，f[i]表示删除i节点后最大联通块的节点数，v代表i的子节点，f[i]=max(max(size[v]),n-size[i]),当i节点作为平衡点删去后，留下的最大联通块的节点数要么是他上面的树的节...

2020-08-08

0 748

双栈排序

思路：要使用2个栈操作使得序列升序，我们可以发现当2个数a[i] a[j]不能放入同一个栈中的时候，要满足条件 i<j<k && a[k]<a[i]<a[j]这里呢，我们用dp[i]表示从i开始到结尾的最小值，不能放到同一个栈中我们就把他分开，这样我们要求的就...

2020-08-07

0 762