[Algorithm][综合训练][消减整数][最长上升子序列(二)][春游]详细讲解

本文主要是介绍[Algorithm][综合训练][消减整数][最长上升子序列(二)][春游]详细讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

1.消减整数

1.题目链接

• 消减整数

---

2.算法原理详解 && 代码实现

• 解法：贪心 + 数学
  • 每次尽可能的减去之前数的两倍，并且能保证可以减到0
  • x % 2a == 0

  #include <iostream>
  using namespace std;int Check(int h)
  {int ret = 0, a = 1;while(h){ret++;h -= a;if(h % (2 * a) == 0){a *= 2;}}return ret;
  }int main()
  {int n = 0, h = 0;cin >> n;while(n--){cin >> h;cout << Check(h) << endl;}
  }
  

---

2.最长上升子序列(二)

1.题目链接

• 最长上升子序列(二)

---

2.算法原理详解 && 代码实现

• 自己的版本：动态规划 -> 50%

  int LIS(vector<int>& nums) 
  {int n = nums.size();vector<int> dp(n, 1);int ret = 1;for(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(nums[j] < nums[i]){dp[i] = max(dp[i], dp[j] + 1);}}ret = max(ret, dp[i]);}return ret;
  }
  

• 优化版本：贪心 + 二分
  • 不关心前面的非递减子序列长什么样子，仅需知道长度为x的子序列末尾是多少即可
  • 存长度为x的所有子序列的末尾时，只用存最小的那个数即可
  • 优化：二分快速寻找插入位置

  int LIS(vector<int>& a)
  {int pos = 0;vector<int> dp(a.size() + 1, 0); // dp[i]: 长度为i的最小末尾// 查找x应该放在哪个位置for(const auto& x : a){// 边界情况处理if(pos == 0 || x > dp[pos]){dp[++pos] = x;}else{// 二分查找插入位置int l = 1, r = pos;while(l < r){int mid = (l + r) / 2;if(dp[mid] >= x){r = mid;}else{l = mid + 1;}}dp[l] = x;}}return pos;
  }
  

---

3.春游

1.题目链接

• 春游

---

2.算法原理详解 && 代码实现

• 解法：贪心 + 分类讨论 --> 细致讨论即可，容易疏漏
  

  #include <iostream>
  using namespace std;long long n = 0, a = 0, b = 0;long long CostTotal(char ch)
  {long long sum = 0;if(ch == 'a'){sum = n / 2 * a;n %= 2;if(n){sum += min(min(a, b), b - a);}}else{sum = n / 3 * b;n %= 3;if(n == 1){sum += min(min(a, b), 2 * a - b);}else if(n == 2){sum += min(min(a, b), 3 * a - b);}}return sum;
  }int main()
  {int t = 0;cin >> t;while(t--){cin >> n >> a >> b;float av = a / 2.0, bv = b / 3.0;if(n <= 2){cout << min(a, b) << endl;continue;}if(av < bv){cout << CostTotal('a') << endl;}else{cout << CostTotal('b') << endl;}}return 0;
  }
  

这篇关于[Algorithm][综合训练][消减整数][最长上升子序列(二)][春游]详细讲解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---