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<

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

ans += dp[ k ] .

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

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #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<
          
            1) { for(i = 0;(1<