#樹形dp#jzoj 1982 數字轉換

題目

如果一個數x的約數和（不包括它本身，下同）比它本身小，那麼x可以變成它的約數和；如果對于某個y>x且y的約數和為x，那麼x也可以變成y。例如，4可以變為3，1可以變為7。限定所有的數字變換在不超過n的正整數範圍内進行，求不斷進行數字變換且沒有重複數字出現的最多變換步數。

分析

這道題是求樹的最長鍊， d 1 i d1_i d1i​表示以i為根的樹到葉子節點的最大值， d 2 i d2_i d2i​表示以i為根的樹到葉子節點的次大值，若 d 1 s o n + d i s i , s o n &lt; d 1 i d1_{son}+dis_{i,son}&lt;d1_i d1son​+disi,son​<d1i​，那麼 d 2 i = d 1 i ， d 1 i = d 1 s o n + d i s i , s o n d2_i=d1_i，d1_i=d1_{son}+dis_{i,son} d2i​=d1i​，d1i​=d1son​+disi,son​

否則，若若 d 1 s o n + d i s i , s o n &lt; d 2 i d1_{son}+dis_{i,son}&lt;d2_i d1son​+disi,son​<d2i​，那麼 d 2 i = d 1 s o n + d i s i , s o n d2_i=d1_{son}+dis_{i,son} d2i​=d1son​+disi,son​

最後掃描所有節點，求 max ⁡ ( d 1 i + d 2 i ) \max(d1_i+d2_i) max(d1i​+d2i​)

代碼

#include <cstdio>
using namespace std;
int n,sum[50001],d1[50001],d2[50001],ans;
int main(){
	freopen("transfer.in","r",stdin);
	freopen("transfer.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	for (int j=2;j<=n/i&&i*j<=n;j++) sum[i*j]+=i;
	for (int i=n;i>=1;i--)
	if (sum[i]<i)
	if (d1[i]+1>d1[sum[i]]) d2[sum[i]]=d1[sum[i]],d1[sum[i]]=d1[i]+1;
	else if (d1[i]+1>d2[sum[i]]) d2[sum[i]]=d1[i]+1;
	for (int i=1;i<=n;i++) if (d1[i]+d2[i]>ans) ans=d1[i]+d2[i];
	return !printf("%d",ans);
}