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