#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>

using namespace std;

const int INF = 1e9;

int ans[65];

void func(int n){
    ans[0] = 0;
    ans[1] = 1;
    ans[2] = 3;
    for(int i = 3; i < n; i++){
        ans[i] = INF;
        for(int j = 0; j < i; j++){
            if((2 * ans[j] + pow(2, i-j) - 1) < ans[i]){
                ans[i] = 2 * ans[j] + pow(2, i-j) - 1;
            }
        }
    }
}

int main(){
    int n;
    func(65);
    while (cin >> n) {
        cout << ans[n] << endl;
    }
    return 0; 
}

参考博客 https://blog.csdn.net/Ice_Alone/article/details/38126433
http://www.360doc.com/content/19/0921/16/9482_862378512.shtml
不好复制,直接去网站看吧。

扩展:多柱问题
https://blog.csdn.net/theljt/article/details/78435460