URAL 1117. Hierarchy

给出一棵中序遍历为1，2，3，4，5，6. . . . .的满二叉树。

然后从编号为 a 的节点发一封信到 编号为 b 的节点。每次只能从 i 传到 (i-1) 或者 (i+1),花费等于路上的点的个数（端点除外）。

问从a 到 b发一封信的最小花费是多少。

尼玛，读题读了一万年，活该CET不过。

dp[ i ] 表示 从 1 到 （i <<1）-1节点的最小花费。

即  dp[ i ] = dp[i-1]*2 + (i-2)*2;

     dp[1] = dp[2] = 0;

设MC(a,b)为 a 到 b 的最小花费，则有

MC(a,b) == MC(b,a) && MC(x,z) == MC(x,y) + MC(y,z) (x < y < z)。

所以问题转化为

MC(a,b) = MC(1,b) - MC(1,a) (b > a)。

MC(1,x)的计算方法：

1,若x <= 1,则MC(1,x) == 0,结束；否则进行下面的步骤。

2,首先找到满足( 1<<k )-1  <  x 的 k 的最大值。

3,减掉与x所在子树平行的最大的左子树及根节点，即将 x 平移到左子树中对应的位置，即 x = x(1<<k);

ans += dp[ k ] .

 4,若x == 0，ans += (k-1) ,结束；否则 ans += (k-1)*2，继续第一步;

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>

#pragma comment(linker, "/STACK:1024000000");
#define LL long long int
#define ULL unsigned long long int
#define _LL __int64
#define INF 0x3f3f3f3f
#define Mod 1000000009

using namespace std;

_LL dp[32];

int main()
{
    int i;

    _LL a,b;

    dp[1] = 0;
    dp[2] = 0;

    for(i = 3;i <= 32; ++i)
    {
        dp[i] = dp[i-1]*2 + (i-2)*2;
    }

    scanf("%I64d %I64d",&a,&b);

    if(a > b)
        swap(a,b);

    _LL temp = 0,ans = 0;

    while(a > 1)
    {
        for(i = 0;(1<<i)-1 < a; ++i)
            ;

        --i;

        a = a - (1<<i);

        if(a == 0)
        {
            ans += dp[i]+(i-1);
            break;
        }
        ans += (dp[i]+(i-1)*2);
    }

    temp = ans;
    ans = 0;

    while(b > 1)
    {
        for(i = 0;(1<<i)-1 < b; ++i)
            ;

        --i;

        b = b - (1<<i);

        if(b == 0)
        {
            ans += dp[i]+(i-1);
            break;
        }
        ans += (dp[i]+(i-1)*2);
    }

    printf("%I64d\n",ans-temp);

    return 0;
}

URAL 1117. Hierarchy,布布扣,bubuko.com

URAL 1117. Hierarchy

原文：http://blog.csdn.net/zmx354/article/details/20146811