AcWing 1075. 숫자 변환 (트 리 DP) 문제 풀이

10746 단어 동적 계획알고리즘
제목 전송 문
만약 에 하나의 x 의 약수 와 y (그 자 체 를 포함 하지 않 음) 가 그 자체 보다 작다 면 x 는 y 가 될 수 있 고 y 도 x 가 될 수 있다.
예 를 들 어 4 는 3, 1 은 7 로 변 할 수 있다.
모든 디지털 변환 을 n 을 초과 하지 않 는 정수 범위 내 에서 한정 하고 디지털 변환 을 계속 진행 하 며 중복 숫자의 최대 변환 단계 가 나타 나 지 않도록 한다.
입력 형식
정수 n 을 입력 하 십시오.
출력 형식
출력 은 끊임없이 디지털 변환 을 진행 하고 중복 숫자의 최대 변환 단계 가 나타 나 지 않 습 니 다.
데이터 범위
1≤n≤50000
입력 예시:
7
출력 예시:
3
예 를 들 어 해석 하 다.
한 가지 방안 은 4 → 3 → 1 → 7 이다.
문제 풀이:
트 리 DP:
먼저 각 수의 약수 의 합 을 미리 처리 하면 우 리 는 모든 합 법 적 인 경 로 를 건설 할 수 있다.
마지막 으로 나 무 를 구 하 는 가장 긴 경로 문제 로 바 뀔 수 있다.
#include
#include
using namespace std;
const int N = 50010;
int n;
int h[N], e[N], ne[N], idx;
int sum[N];
bool vis[N];
int ans;
void add(int a, int b)
{
     
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfs(int u)   //  u         
{
     
   int d1 = 0, d2 = 0;  //           
   for(int i = h[u]; i != -1; i = ne[i]){
     
       int j = e[i];
       int d = dfs(j) + 1;
       if(d >= d1){
     
           d2 = d1;
           d1 = d;
       }
       else if(d >= d2)d2 = d;
   }
   ans = max(ans, d1 + d2);
   return d1;
}
int main()
{
     
    cin >> n;
    for(int i = 1; i <= n; i++)     //            
        for(int j = 2; j <= n / i; j++)
            sum[i * j] += i;  
    memset(h, -1, sizeof h); //1      0，    2    
    for(int i = 2; i <= n; i++){
        
        if(i > sum[i]){
        //         
            add(sum[i], i);
            vis[i] = true;  //    
        }
    }
    for(int i = 1; i <= n; i++){
     
        if(!vis[i]){
        //       
            dfs(i);
        }
    }
    cout << ans << endl;
    return 0;
}
Round G - D (Simple Polygon)
JSP 필수 이해 요소

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage