当前位置：首页 > news >正文

[Algorithm][综合训练][体育课测验(二)][合唱队形][宵暗的妖怪]详细讲解

news 来源：原创 2024/9/16 14:06:15

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