---

1.体育课测验(二)

1.题目链接

• 体育课测验(二)

---

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

• 说明：单纯积累一题[拓扑排序]用于加强印象
  • 能识别模型，并且写出代码

   vector<int> findOrder(int n, vector<vector<int> >& groups) {vector<vector<int>> edges(n);vector<int> in(n);// 1.建图for(auto v : groups){int a = v[0], b = v[1]; // b -> aedges[b].push_back(a);in[a]++;}// 2.入度为0的点，加入到队列中queue<int> q;for(int i = 0; i < n; i++){if(in[i] == 0){q.push(i);}}// 3.拓扑排序vector<int> ret;while(q.size()){int tmp = q.front();q.pop();ret.push_back(tmp);for(auto x : edges[tmp]){if(--in[x] == 0){q.push(x);}}}if(ret.size() == n){return ret;}else{return {};}}
  

---

2.合唱队形

1.题目链接

• 合唱队形

---

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

• 问题转化：依次枚举任意位置的同学，将其作为山峰位置，找出最长的x + y - 1
  

• 解法：动态规划 -> 最长递增子序列模型

  • 状态表示：dp[i]：以i位置为结尾的所有子序列中，最长上升子序列的长度
    • f[i]：以i位置同学为结尾的最长上升子序列的长度
    • g[i]：以i位置同学为结尾的最长上升子序列的长度(从后向前看)
  • 状态转移方程：
    

  #include <iostream>
  #include <vector>
  using namespace std;int main()
  {int n = 0;cin >> n;vector<int> nums(n, 0), f(n, 1), g(n, 1);for(auto& x : nums){cin >> x;}// 从前向后for(int i = 0; i < n; i++){for(int j = 0; j < i; j++){if(nums[j] < nums[i]){f[i] = max(f[i], f[j] + 1);}}}// 从后向前for(int i = n - 1; i >= 0; i--){for(int j = i + 1; j < n; j++){if(nums[i] > nums[j]){g[i] = max(g[i], g[j] + 1);}}}int len = 0;for(int i = 0; i < n; i++){len = max(len, f[i] + g[i] - 1);}cout << n - len << endl;return 0;
  }
  

---

3.宵暗的妖怪

1.题目链接

• 宵暗的妖怪

---

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

• 解法：动态规划 --> 线性DP

  • 状态表示：dp[i]：从[1, n]区间内吞噬黑暗，最大的饱食度是多少

  • 状态转移方程：
    

  • 初始化：
    

  • 返回值：dp[n]

  #include <iostream>
  #include <vector>
  using namespace std;int main()
  {int n = 0;cin >> n;vector<long long> nums(n + 1, 0), dp(n + 1, 0);for(int i = 1; i <= n; i++){cin >> nums[i];}for(int i = 3; i <= n; i++){dp[i] = max(dp[i - 1], dp[i - 3] + nums[i - 1]);}cout << dp[n] << endl;return 0;
  }