#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