[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;
}