kotori和糖果

递推题 合并成一堆的最小代价肯定是分成尽可能相等的两堆 再加上这两堆合并的代价(不是0就是1) 那么就这样一直递推下去
设堆数为n， 记合并代价为dp[n]

1. 如果堆数是奇数 那么dp[n] = dp[n/2] + dp[n/2 + 1] + 1
2. 如果堆数是偶数 那么dp[n] = 2 * dp[n/2] 可以对前10000项进行动态规划 再递归求出最小代价

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 10010;
ll dp[N];

ll dfs(ll x){
  if (x <= 10000) return dp[x];
  if (x % 2) return dfs(x / 2) + dfs(x / 2 + 1) + 1;
  else return 2 * dfs(x / 2);
}

int main () {
  dp[1] = 0, dp[2] = 0;
  for (int i = 3;i <= 10000; ++ i) {
    if (i % 2) dp[i] = dp[i / 2] + dp[i / 2 + 1] + 1;
    else dp[i] = 2 * dp[i / 2];
  }
  int t;cin >> t;
  while (t--) {
    ll n;cin >> n;
    cout << dfs(n) << '\n';
  }
}