1. 宝石

动态规划，dp[i]表示到第i关可以获得的最大金币数量。

dp[i] = dp[i-1]，第i关是boss

dp[i] = max(dp[i-1], dp[j-1] + Vk)，j是离i最近的获得宝石k的关卡。

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> dp(n + 1, 0);
    unordered_map<int, int> collections;
    for (int i = 1; i <= n; ++i)
    {
        char boss;
        int type;
        int value;
        cin >> boss >> type >> value;
        if (boss == 'b')
        {
            collections[type] = i;
            dp[i] = dp[i - 1];
        }
        else
        {
            if (!collections.count(type))
            {
                dp[i] = dp[i - 1];
            }
            else
            {
                dp[i] = max(dp[i - 1], dp[collections[type]] + value);
            }
        }
    }

    cout << dp[n];
    return 0;
}

2. 修路

#include <bits/stdc++.h>

using namespace std;

int dfs(int start, vector<vector<pair<int, int>>>& adj, vector<int> &visited){
  visited[start] = true;
  if(adj[start].size() == 0){
    return 0;
  }
  int res = 0;
  for(auto next : adj[start]){
    if(visited[next.first]){
      continue;
    }
    int next_count = dfs(next.first, adj, visited);
    if(next_count > 0){
      res += next_count;
    }
    else if(next.second){
      res += 1;
    }
  }
  return res;
}


int main(){
  int n;
  cin >> n;
  vector<vector<pair<int, int>>> adj(n+1, vector<pair<int, int>>());
  for(int i = 0; i < n-1; ++i){
    int start, end, is_bad;
    cin >> start >> end >> is_bad;
    adj[start].push_back({end, is_bad});
    adj[end].push_back({start, is_bad});
  }
  vector<int> visited(n+1, 0);
  int res = dfs(1, adj, visited);
  cout << res;
  return 0;
}

3. 最大积连续子数组的开始下标和结束下标

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int main(){
  int n;
  cin >> n;
  vector<int> nums(n);
  for(int i = 0; i < n; ++i){
    cin >> nums[i];
  }
  vector<ll> max_dp(n, LLONG_MIN);  //max_dp[i]以下标i结束的连续子数组的最大积
  vector<ll> min_dp(n, LLONG_MAX);  //min_dp[i]以下标i结束的连续子数组的最小积

  vector<int> max_start(n, 0);      //max_start[i] 表示以下标i结束的最大积连续子数组的起始下标
  vector<int> min_start(n, 0);      //min_start[i] 表示以下标i结束的最小积连续子数组的起始下标

  int res_start = 0;
  int res_end = 0;
  ll res_max = nums[0];
  max_dp[0] = nums[0];
  min_dp[0] = nums[0];
  for(int i = 1; i < n; ++i){
    if(nums[i] == 0){
      max_dp[i] = 0;
      min_dp[i] = 0;
      max_start[i] = 0;
      min_start[i] = 0;
    }
    else if(nums[i] > 0){
      if(nums[i] > max_dp[i-1] * nums[i]){
        max_dp[i] = nums[i];
        max_start[i] = i;
      }
      else{
        max_dp[i] = max_dp[i-1] * nums[i];
        max_start[i] = max_start[i-1];
      }
      if(nums[i] < min_dp[i-1] * nums[i]){
        min_dp[i] = nums[i];
        min_start[i] = i; 
      }
      else{
        min_dp[i] = min_dp[i-1] * nums[i];
        min_start[i] = min_start[i-1];
      }
    }
    else{
      if(nums[i] > min_dp[i-1] * nums[i]){
        max_dp[i] = nums[i];
        max_start[i] = i;
      }
      else{
        max_dp[i] = min_dp[i-1] * nums[i];
        max_start[i] = max_start[i-1];
      }
      if(nums[i] < max_dp[i-1] * nums[i]){
        min_dp[i] = nums[i];
        min_start[i]  = i;
      }
      else{
        min_dp[i] = max_dp[i-1] * nums[i];
        min_start[i]  = min_start[i-1];
      }
    }
    if(max_dp[i] > res_max){
      res_max = max_dp[i];
      res_start = max_start[i];
      res_end = i;
    }
    else if(max_dp[i] == res_max && i - max_start[i] > res_end - res_start){
      res_start = max_start[i];
      res_end = i;
    }
  }
  if(res_max <= -1){
    cout << -1;
  }
  else{
    cout << res_start << " " << res_end;
  }
  return 0;
}

4. 使数组成为非严格递增数组的最小操作次数

#include <bits/stdc++.h>

using namespace std;

int scan_num(vector<int>& nums){
  for(int i = 1; i < nums.size(); ++i){
    if(nums[i-1] > nums[i]){
      return i-1;
    }
  }
  return -1;
}

int main(){
  int t;
  cin >> t;
  while(t--){
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
      cin >> nums[i];
    }
    int count = 0;
    int index = scan_num(nums);
    while(index != -1){
      count++;
      for(int i = 0; i < nums.size(); i++){
        if(nums[i] == nums[index]){
          nums[i] = 0;
        }
      }
      index = scan_num(nums);
    }
    cout << count;
  }
  return 0;
}