sreffo：刚收到华为说进入offer池的通知了 感谢各位大佬们之前的回复

事无巨细，悉究本末：我是算法岗，第一题排列小球，过了100%，第二题没过，就不说了 第一题递归的方***超时，主要是有重复计算，使用数组保存结果就好了，避免重复计算，是动规的思想。 动规用四维数组保存状态值，用四元组表示一个状态（上一个球的颜色，P球的剩余数量，Q球的剩余数量，R球的剩余数量），上一个球颜色为-1表示初始状态，说明下一个球可以是任意球，上一个球为0表示为P球，下一个球只能为Q或者R，上一个球为Q球、R球时同理。 递归代码： #include <bits/stdc++.h> using namespace std; int total; int dfs(vector<int>& nums, int last, int len) {  if (len == total)   return 1;  int cnt = 0;  for (int i = 0; i < 3; i++)  {   if (i != last && nums[i] > 0)   {    nums[i]--;    cnt += dfs(nums, i, len + 1);    nums[i]++;   }  }  return cnt; } int main() {  vector<int> nums(3, 0);  for (int i = 0; i < 3; i++)  {   cin >> nums[i];   total += nums[i];  }  int res = dfs(nums, -1, 0);  cout << res << endl;     return 0; } 动规代码： #include <bits/stdc++.h> using namespace std; long total; long dfs(vector<long>& nums, long last, long len, vector<vector<vector<vector<long>>>>& dp) {  if (len == total)   return 1;     if(dp[last + 1][nums[0]][nums[1]][nums[2]] > 0) {         return dp[last + 1][nums[0]][nums[1]][nums[2]];     } else {         long cnt = 0;         for (int i = 0; i < 3; i++)         {             if (i != last && nums[i] > 0)             {                 nums[i]--;                 cnt += dfs(nums, i, len + 1, dp);                 nums[i]++;             }         }         dp[last + 1][nums[0]][nums[1]][nums[2]] = cnt;         return cnt;     } } int main() {  vector<long> nums(3, 0);  for (int i = 0; i < 3; i++)  {   cin >> nums[i];   total += nums[i];  }     vector<vector<vector<vector<long>>>> dp(4, vector<vector<vector<long>>>(nums[0] + 1, vector<vector<long>>(nums[1] + 1, vector<long>(nums[2] + 1, 0))));  long res = dfs(nums, -1, 0, dp);  cout << res << endl;     return 0; } 动规代码是从递归改过来的，可能不是太简洁。查看图片

tjmath：三角形那个题是这样，先排个序，令X<=Y<=Z，不妨设三边分别为a b c 对任意a 当b \in [1,min(a,Z-a)) 时 c的取值有 [a-b+1,a+b-1]一共 2b-1个 求和后有 (min(a,Z-a)-1)^2个 当 b \in (Z-a,a)时 c 的取值有 [a-b+1, Z] 共 Z-a+b 个 求和后等于 （1.5Z-a)(2a-Z-1) 当 b \in (a,Z-a)时 c的取值有[b-a+1,b-a-1] 共 2a-1个 求和后等于 (2a-1)*(Z-2a-1) 当 b == a时 c的取值为[1, min(2a-1,Z)] 当 b == Z-a时 c的取值为[abs(a-b)+1,Z-1] 最后当 b \in (max(a,Z-a), Y]时 c的取值为[b-a+1,Z]共Z-b+a个 求和为（Z+a-(Y+max(a,Z-a)+1)/2)(Y-max(a,Z-a)) 循环a即可，复杂度O(X)