题目描述：
给定一个n，把n给打倒，然后递归的求出包含n在内的上面所有的会倒下的瓶子值的平方和。
这里使用二分先求出目前给定的n的行号i和列号j。观察可以发现，对于所有的列号j，j=1或者j=i时，是需要考虑往上单边的总和，其他情况都有两个分支。
再观察可以发现，两个分支在再上一行的重合部分，会被dfs多计算一遍，所以减去这一部分即可。
把计算结果用map保存，减少重复计算。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define int long long 6 7 map<pair<int, int>, int> mp; 8 9 int dfs(int i, int j) 10 { 11 if (mp.count({i, j})) { 12 return mp[{i, j}]; 13 } 14 if (j > i || j <= 0) { 15 return mp[{i, j}] = 0; 16 } 17 int s = i * (i - 1) / 2 + j; 18 if (j == 1 || j == i) { 19 return mp[{i, j}] = s * s + dfs(i - 1, j) + dfs(i - 1, j - 1); 20 } else { 21 return mp[{i, j}] = s * s + dfs(i - 1, j) + dfs(i - 1, j - 1) - dfs(i - 2, j - 1); 22 } 23 } 24 25 void solve() 26 { 27 int n; 28 cin >> n; 29 int l = 1, r = 2023; 30 while (l < r) { 31 int mid = (l + r) >> 1; 32 if ((1 + mid) * mid / 2 >= n) { 33 r = mid; 34 } else { 35 l = mid + 1; 36 } 37 } 38 int curRow = l; 39 int curPos = n - curRow * (curRow - 1) / 2; 40 mp[{1, 1}] = 1; 41 cout << dfs(curRow, curPos) << endl; 42 43 } 44 45 int32_t main() 46 { 47 ios_base::sync_with_stdio(false); 48 cin.tie(nullptr); cout.tie(nullptr); 49 50 int t = 1; 51 cin >> t; 52 while (t--) { 53 solve(); 54 } 55 56 return 0; 57 }