$Loj10155$ 数字转换(求树的最长链) 树形$DP$

loj

Description

如果一个数x的/约数和/y(不包括他本身)比他本身小,那么x可以变成y,y 也可以变成x.限定所有数字变换在不超过n的正整数范围内进行,求不断进行数字变换且不出现重复数字的最多变换步数.

注意断句QwQ,是x的/约数和/y,不是x的约数/和/y

Sol

先预处理出每个数的约数和,将可以转换的数连边

可将数x的约数和y看成x的父结点,将以x为约数和的数看成x的子结点,这显然是一棵树

题目也就转换成了求这棵数的最长链

对于结点x,只要维护在以之为根的树内一端为x的最长链与次长链即可

(感觉上面那句话写得很凌乱,所以就自己打空格断句了)

具体来说,d1[x]表示最长链的长度,d2[x]表示次长链的长度,y是x的孩子

if(d1[y]+1>d1[x]) d2[x]=d1[x],d1[x]=d1[y]+1;

else d2[x]=max(d2[x],d1[y]+1);

之前在想为什么不是 if(d1[y]+1>d1[x]) d2[x]=max(d1[x],d2[y]+1),d1[x]=d1[y]+1;

也就是为什么y的次长链不能更新x的次长链,发现其实d1[x]与d2[x]不能x的同一棵子树中的!

画图理解一下

如果d1[1]和d2[1]都在右子树中,那么d1[1]+d2[1]所构成的链是图中红色箭头所表示的那样,实际并不能算是树中的一条链

Code

 #include<iostream>

 #include<cstdio>

 #define Rg register

 #define il inline

 #define go(i,a,b) for(Rg int i=a;i<=b;++i)

 #define yes(i,a,b) for(Rg int i=a;i>=b;--i)

 using namespace std;

 il int read()

 {

     int x=,y=;char c=getchar();

     while(c<''||c>''){if(c=='-')y=-;c=getchar();}

     while(c>=''&&c<=''){x=(x<<)+(x<<)+c-'';c=getchar();}

     return x*y;

 }

 const int N=;

 int n,ans,a[N],d1[N],d2[N];

 int main()

 {

     n=read();

     go(i,,n)

         go(j,,n/i)a[i*j]+=i;

     yes(x,n,)

     {

         int y=a[x];if(y>=x)continue;

         if(d1[y]<d1[x]+){d2[y]=d1[y],d1[y]=d1[x]+;}

         else d2[y]=max(d2[y],d1[x]+);

     }

     go(i,,n)ans=max(ans,d1[i]+d2[i]);

     printf("%d\n",ans);

     return ;

 }

巴特西

$Loj10155$ 数字转换(求树的最长链) 树形$DP$

最新文章

热门文章