首页 > 其他分享 >CF868E Policeman and a Tree 题解

CF868E Policeman and a Tree 题解

时间:2023-09-08 14:46:38浏览次数:42  
标签:head 55 int 题解 CF868E Tree read et void

Description.

树上警察抓小偷。一名警察速度为 \(1\),多名小偷速度为 \(+\infty\),问多长时间抓到。
树点数 \(\le 50\)

Solution.

首先不可能抓不到。
其次步数不可能超过 \(2500\)(每抓完一个小偷走一遍全图)。
这启发我们可以直接暴搜每一步,并记忆化。
如果状态设为当前在 \(x\),那么 \(x\) 的各个字数内的小偷数量是影响答案的,无法记录状态。
注意到警察不会在非叶子节点走回头路,因为他没抓完一个子树的小偷怎么会回头。
所以可以记录警察移动过程,并把这个当做状态。
相当于记录了一个边,然后这条边把树切开,只需记录两边各多少小偷即可。
同时注意这是一个博弈问题,所以 dp 过程中既有 \(\min\) 又有 \(\max\)。

Coding.

点击查看代码
//是啊……你就是那只鬼了……所以被你碰到以后,就轮到我去变成鬼了……{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
        char c=getchar(),f=0;x=0;
        for(;c<48||c>57;c=getchar()) if(c==45) f=1;
        for(;c>=48&&c<=57;c=getchar()) x=(x<<3)+(x<<1)+(c^48);
        f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
struct edge{int to,w,nxt;}e[105];int n,et,head[55],dg[55];
inline void adde(int x,int y,int w) {e[++et]=(edge){y,w,head[x]},head[x]=et,dg[y]++;}
int S,m,cn[55],dp[105][55][55];
inline void count(int x,int fa)
{
        for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa)
                count(e[i].to,x),cn[x]+=cn[e[i].to];
}
inline int dfs(int E,int a,int b)
{
        int &T=dp[E][a][b],x=e[E].to,fa=e[E^1].to;if(T) return T;
        //printf("%d -> %d , %d %d : ??\n",e[E^1].to,e[E].to,a,b);
        if(dg[x]==1) return b?T=dfs(E^1,b,0)+e[E].w:0;
        int g[55];memset(g,0,sizeof(g)),g[0]=1e9;
        for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa)
                for(int j=a;j;j--) for(int k=j;k;k--)
                        g[j]=max(g[j],min(g[j-k],dfs(i,k,a+b-k)+e[i].w));
        //printf("%d -> %d , %d %d : %d\n",e[E^1].to,e[E].to,a,b,g[a]);
        return T=g[a];
}
int main()
{
        read(n),et=1;for(int i=1,x,y,w;i<n;i++) read(x,y,w),adde(x,y,w),adde(y,x,w);
        read(S,m);for(int i=1,x;i<=m;i++) read(x),cn[x]++;
        count(S,S);int rs=1e9;for(int i=head[S];i;i=e[i].nxt)
                rs=min(rs,dfs(i,cn[e[i].to],m-cn[e[i].to])+e[i].w);
        return printf("%d\n",rs),0;
}

标签:head,55,int,题解,CF868E,Tree,read,et,void
From: https://www.cnblogs.com/pealfrog/p/17687532.html

相关文章

  • elementui tree 获取选中子节点的所有父级节点信息
    //获取选中的节点constcheckedNodes=this.$refs.rolePermissionsTree.getCheckedNodes(false,true)//获取选中节点的所有父级节点checkedNodes.forEach(node=>{console.log(node)})效果如下......
  • 【题解】《PTA-Python程序设计》题目集分享
    第1章-1从键盘输入两个数,求它们的和并输出(30分)本题目要求读入2个整数A和B,然后输出它们的和。输入格式:在一行中给出一个被加数在另一行中给出一个加数输出格式:在一行中输出和值。输入样例:在这里给出一组输入。例如:18-48输出样例:在这里给出相应的输出。例如:......
  • 题解 P8165 [eJOI2021] AddK
    不知道为什么这道题还没有题解。Solution对于操作\(1\),由于\(K\le10\),直接暴力单点修改即可。而操作\(2\)的询问,不难发现,最后结果的呈现形式是\[1\timesA_l+2\timesA_{l+1}+3\timesA_{l+2}+...+3\timesA_{r-2}+2\timesA_{r-1}+1\timesA_r\]其中中间可能有一段系数......
  • [element-ui] el-tree 懒加载load
    懒加载:点击节点时才进行该层数据的获取。注意:使用了懒加载之后,一般情况下就可以不用绑定:data。<el-tree:props="props":load="loadNode"lazy></el-tree>懒加载—由于在点击节点时才进行该层数据的获取,默认情况下Tree无法预知某个节点是否为叶子节点,所以会为每个节点添加一个......
  • SP8177 题解
    2023-09-0111:29:13solution题意:每次询问\([l,r]\)内有多少个数满足可以被所有非\(0\)数位整除。思路看到这个数据范围和题目描述,显然是数位dp。因为\(1\sim9\)的最小公倍数是\(2520\),并且\(2520\)是其他所有\(1\sim9\)子集的最小公倍数的倍数,所以我们只需要......
  • CF402D 题解
    2023-09-0418:42:46solution不难想到我们要先记录一下每一位的前缀\(\gcd\),我们发现我们选择一位的前缀\(\gcd\)除掉以后,前缀\(\gcd\)会变为\(1\)并且会导致这位之后的\(\gcd\)全部为\(1\)。所以每一位只能选择一次,并且我们从后往前扫肯定比从前往后扫要更优。我们......
  • wzOI 2023.8.31 题解
    2023-09-0115:59:41$$前言$$太菜了,第一题都打成那样了没发现是MST,第三题数据范围没有很仔细看,以为是乱搞(组合之类的)题就直接跳了。不得不说这次比赛题目的一些思路还是挺妙的,一些想法确实我这种成分想不太到。$$A$$$$题意$$给出了\(m\)个可以查询的区间\([L_i,R_i]\)......
  • CF1103C 题解
    2023-09-0514:52:07solution找路径很好找,我们随便跑个dfs树找个深度\(\ge\frac{n}{k}\)的路径输出即可。可是怎么找\(k\)个长度不是\(3\)的倍数的环呢?既然我们跑了dfs树,那么就没有横叉边,对于叶子节点非树边只有返祖边,然后一看这个很奇怪的条件——保证每个点度数大......
  • CF1851 部分题解
    2023-07-3019:35:02前言因为我实在是太菜了,没时间也不会做最后两题,所以这里只有前\(5\)道签到题的题解。之后我有时间看了后两题的题解再来更新吧~A先不用看那么多七七八八的,搞清楚下面几点即可:高度不能相同。高度差得被整除。高度差不能太大。好了,然后就可以\(AC\)......
  • 暑假集训Day19 比赛题解
    2023-08-0516:22:13总结这次打下来,由于T2贪心不够完全,T3模拟\(5\)个时不是最优,T4想到暴力做法但是来不及打,加之全都是捆绑测试点,导致我T2,T3虽然加起来有不少点对了,但是还是判全错,最后也只剩下T1的100。感觉这次前三题也不难,都是可做的,T4的30pts暴力也很白给,但......