问题 A: 最大连续子序列
题目描述
给定K个整数的序列{ N1, N2, …, NK }，其任意连续子序列可表示为{ Ni, Ni+1, …, Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和为20。现在增加一个要求，即还需要输出该子序列的第一个和最后一个元素。
输入
测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K( K<= 10000 )，第2行给出K个整数，中间用空格分隔，每个数的绝对值不超过100。当K为0时，输入结束，该用例不被处理。
输出
对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。
样例输入 复制
5
-3 9 -2 5 -4
3
-2 -3 -1
0
样例输出 复制
12 9 5
0 -2 -1
思路
dp[i] = max(dp[i-1]+a[i], a[i])
运用和多标度迪杰斯特拉类似的思想，多设置一个状态数组 l[N] 用于记录最优解对应的序列长度，在状态更新时同步进行更新。同时设置一个变量存储最优解对应的下标。
代码
#include<iostream>
using namespace std;
const int N = 10010;
int dp[N], a[N], l[N];
// dp[i] = max(a[i], dp[i-1]+a[i])
int main(void) {
int k;
while (cin >> k, k != 0) {
int ans = 0, idx;
bool flag = true;
for (int i = 1; i <= k; i ++ ) {
cin >> a[i];
if (a[i] > 0) flag = false;
// dp[i] = max(a[i], dp[i-1]+a[i]);
if (dp[i-1]+a[i] > a[i]) {
dp[i] = dp[i-1]+a[i];
l[i] = l[i-1] + 1;
}
else {
dp[i] = a[i];
l[i] = 1;
}
if (dp[i] > ans) {
ans = dp[i];
idx = i;
}
}
if (flag) {
printf("0 %d %d\n", a[1], a[k]);
continue;
}
printf("%d %d %d\n", ans, a[idx - l[idx] + 1], a[idx]);
}
}
问题 A: 最长上升子序列
一个数列ai如果满足条件a1 < a2 < … < aN，那么它是一个有序的上升数列。我们取数列(a1, a2, …, aN)的任一子序列(ai1, ai2, …, aiK)使得1 <= i1 < i2 < … < iK <= N。例如，数列(1, 7, 3, 5, 9, 4, 8)的有序上升子序列，像(1, 7)， (3, 4, 8)和许多其他的子序列。在所有的子序列中，最长的上升子序列的长度是4，如(1, 3, 5, 8)。
现在你要写一个程序，从给出的数列中找到它的最长上升子序列。
输入
输入包含两行，第一行只有一个整数N（1 <= N <= 1000），表示数列的长度。
第二行有N个自然数ai，0 <= ai <= 10000，两个数之间用空格隔开。
输出
输出只有一行，包含一个整数，表示最长上升子序列的长度。
样例输入 复制
7
1 7 3 5 9 4 8
样例输出 复制
4
思路
dp[i] = max(dp[j]+1, 1) for j < i && a[j] < a[i]
代码
#include<iostream>
#include<algorithm>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int n, m;
int a[N], dp[N];
// dp[i] = max(dp[j]+1, 1) for j < i && a[j] < a[i]
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i ++ ) {
cin >> a[i];
dp[i] = 1;
for (int j = 1; j < i; j ++ ) {
if (a[j] < a[i]) {
dp[i] = max(dp[j] + 1, dp[i]);
}
}
m = max(m, dp[i]);
}
cout << m << '\n';
return 0;
}
1020.潜水员
- 题目
- 提交记录
- 讨论
- 题解
- 视频讲解
潜水员为了潜水要使用特殊的装备。
他有一个带2种气体的气缸：一个为氧气，一个为氮气。
让潜水员下潜的深度需要各种数量的氧和氮。
潜水员有一定数量的气缸。
每个气缸都有重量和气体容量。
潜水员为了完成他的工作需要特定数量的氧和氮。
他完成工作所需气缸的总重的最低限度的是多少？
例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。
你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。
输入格式
第一行有2个整数 m，n�，�。它们表示氧，氮各自需要的量。
第二行为整数 k� 表示气缸的个数。
此后的 k� 行，每行包括ai，bi，ci��，��，��，3个整数。这些各自是：第 i� 个气缸里的氧和氮的容量及气缸重量。
输出格式
仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。
数据范围
1≤m≤211≤�≤21,
1≤n≤791≤�≤79,
1≤k≤10001≤�≤1000,
1≤ai≤211≤��≤21,
1≤bi≤791≤��≤79,
1≤ci≤8001≤��≤800
输入样例：
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
输出样例：
249
思路
代码
#include<iostream>
#include<algorithm>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 100;
int n, m, k;
int dp[N][N][N]; // dp[i][j][k] 表示从前 i 个物品中选氧含量不低于 j，氮含量不低于 k 的气缸的重量总和的最低值
// dp[i][j][k] = min(dp[i-1][j-w1i][k-w2k] + vi, dp[i-1][j][k])
// 特殊之处：当 j < w1i || k < w2k 时，dp[i-1][j-w1i][k-w2k] = 0;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
for (int i = 0; i <= n; i ++ )
for (int j = 0; j <= m; j ++ )
dp[0][i][j] = 0x3f3f3f3f;
dp[0][0][0] = 0;
for (int i = 1; i <= k; i ++ ) {
int a, b, c;
cin >> a >> b >> c;
for (int j = 0; j <= n; j ++ ) {
for (int k = 0; k <= m; k ++ ) {
dp[i][j][k] = min(dp[i-1][max(j-a, 0)][max(k-b, 0)] + c, dp[i-1][j][k]);
}
}
}
cout << dp[k][n][m] << '\n';
return 0;
}
求具体方案
https://www.acwing.com/problem/content/12/
思路
反过来求，用判断的方式一步步找出方案做出了什么选择。
字典序 -> 贪心
代码
#include<iostream>
#include<algorithm>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int n, m;
int f[N][N], w[N], v[N];
// f[i][j] = max(f[i+1][j], f[i+1][j-v[i]]+w[i]);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
for (int i = n; i >= 1; i -- ) {
for (int j = 0; j <= m; j ++ ) {
f[i][j] = f[i+1][j];
if (j >= v[i]) f[i][j] = max(f[i][j], f[i+1][j-v[i]]+w[i]);
}
}
// cout << f[1][m] << '\n';
int j = m;
for (int i = 1; i <= n; i ++ ) {
if (j - v[i] >= 0 && f[i][j] == f[i+1][j - v[i]] + w[i]) {
cout << i << ' ';
j -= v[i];
}
}
return 0;
}
分组背包问题
思路
代码
#include<iostream>
#include<algorithm>
#include<cstring> // memset
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 20;
int n, m;
int dp[N][N];
int w[N][N], v[N][N];
// dp[i][j] 表示从前 i 家公司选，设备数不超过 j 的选法中，盈利的最大值
// 分组背包问题：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i, 1]]+v[i, 1], ... )
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
cin >> w[i][j];
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= m; j ++ )
for (int k = 0; k <= j; k ++ )
dp[i][j] = max(dp[i][j], dp[i-1][j-k]+w[i][k]);
cout << dp[n][m] << '\n';
int j = m;
for (int i = n; i ; i -- ) {
int flag = false;
for (int k = 1; k <= m; k ++ ) {
if (j-k>= 0 && dp[i][j] == dp[i-1][j-k]+w[i][k]) {
cout << i << ' ' << k << '\n';
j -= k;
flag = true;
break;
}
}
if (!flag) cout << i << ' ' << 0 << '\n';
}
return 0;
}
力扣每日一题 2580. 统计将重叠区间合并成组的方案数
给你一个二维整数数组 ranges ，其中 ranges[i] = [starti, endi] 表示 starti 到 endi 之间（包括二者）的所有整数都包含在第 i 个区间中。
你需要将 ranges 分成 两个 组（可以为空），满足：
- 每个区间只属于一个组。
- 两个有 交集 的区间必须在 同一个 组内。
如果两个区间有至少 一个 公共整数，那么这两个区间是 有交集 的。
- 比方说，区间
[1, 3]和[2, 5]有交集，因为2和3在两个区间中都被包含。
请你返回将 ranges 划分成两个组的 总方案数 。由于答案可能很大，将它对 109 + 7 取余 后返回。
示例 1：
输入：ranges = [[6,10],[5,15]]
输出：2
解释：
两个区间有交集，所以它们必须在同一个组内。
所以有两种方案：
- 将两个区间都放在第 1 个组中。
- 将两个区间都放在第 2 个组中。
示例 2：
输入：ranges = [[1,3],[10,20],[2,5],[4,8]]
输出：4
解释：
区间 [1,3] 和 [2,5] 有交集，所以它们必须在同一个组中。
同理，区间 [2,5] 和 [4,8] 也有交集，所以它们也必须在同一个组中。
所以总共有 4 种分组方案：
- 所有区间都在第 1 组。
- 所有区间都在第 2 组。
- 区间 [1,3] ，[2,5] 和 [4,8] 在第 1 个组中，[10,20] 在第 2 个组中。
- 区间 [1,3] ，[2,5] 和 [4,8] 在第 2 个组中，[10,20] 在第 1 个组中。
提示：
1 <= ranges.length <= 105ranges[i].length == 20 <= starti <= endi <= 109
思路
很多个区间，排序！嗯！
首先根据每个区间的左端点进行排序，再遍历一遍就能得到合并之后，不相交的区间个数 。答案就是
代码
我的
class Solution {
public:
int countWays(vector<vector<int>>& ranges) {
typedef pair<int, int> PII;
vector<PII> a(ranges.size());
for (int i = 0; i < ranges.size(); i ++ )
a[i] = {ranges[i][0], ranges[i][1]};
sort(a.begin(), a.end());
int prel = a[0].first, prer = a[0].second, cnt = 1;
for (int i = 1; i < a.size(); i ++ ) {
int l = a[i].first, r = a[i].second;
if (l > prer) {
cnt ++ ;
prel = l, prer = r;
continue;
}
prel = l, prer = r;
}
cout << cnt << endl;
return cnt;
}
};
优雅的
class Solution {
public:
int countWays(vector<vector<int>>& ranges) {
int n = ranges.size();
sort(ranges.begin(), ranges.end(),
[](auto& a, auto& b) { return a[0] < b[0]; });
int res = 2, r = ranges[0][1];
for (int i = 1; i < n; ++i) {
if (ranges[i][0] > r) {
res = res * 2 % 1000000007;
}
r = max(r, ranges[i][1]);
}
return res;
}
};
优雅之处：
- 匿名函数比较，省去我用 pair
- 由于底数确定，没必要专门写快速幂
这两份代码都是用来解决同一个问题的，但是它们的实现方式和风格有所不同。让我们来对比一下：
你的代码
你的代码使用了更传统的编程风格，包括显式类型定义和循环。你首先创建了一个 pair<int, int> 类型的向量 a，然后遍历 ranges 来填充 a。然后，你对 a 进行了排序，并使用了一个循环来计算结果。你的代码更加详细和直观，容易理解。
优雅的代码
这份代码使用了更现代的 C++ 特性，如 auto 关键字和 lambda 表达式。它首先对 ranges 进行排序，然后使用一个循环来计算结果。这份代码更加简洁，但可能需要读者对 C++ 的一些高级特性有所了解。
1383. 最大的团队表现值
给定两个整数 n 和 k，以及两个长度为 n 的整数数组 speed 和 efficiency。现有 n 名工程师，编号从 1 到 n。其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。
从这 n 名工程师中最多选择 k 名不同的工程师，使其组成的团队具有最大的团队表现值。
团队表现值 的定义为：一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。
请你返回该团队的最大团队表现值，由于答案可能很大，请你返回结果对 10^9 + 7 取余后的结果。
示例 1：
输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
输出：60
解释：
我们选择工程师 2（speed=10 且 efficiency=4）和工程师 5（speed=5 且 efficiency=7）。他们的团队表现值为 performance = (10 + 5) * min(4, 7) = 60 。
示例 2：
输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
输出：68
解释：
此示例与第一个示例相同，除了 k = 3 。我们可以选择工程师 1 ，工程师 2 和工程师 5 得到最大的团队表现值。表现值为 performance = (2 + 10 + 5) * min(5, 4, 7) = 68 。
示例 3：
输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
输出：72
思路
这道题的思想是贪心。
基于团队值的定义：「所有工程师速度的和」乘以他们「效率值中的最小值」
我们不难想到，给定一个团队，「效率值中的最小值」是由一个人决定的。因此我们可以用枚举的方式固定这一项，再去考虑「所有工程师速度的和」。
如何枚举？如果我们希望固定，那么枚举的应该是一定范围内的最小值，因此可以按照效率降序排序，这样考虑前 个工程师的时候，第
个工程师的效率值便是最低的。
同时，我们只需要考虑这前 个工程师中的「（前
大的所有工程师速度的和」的最大值。
很自然可以想到用堆来维护这样一个值。图解
代码
class Solution {
public:
int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
const int mod = 1000000007;
typedef pair<int, int> PII;
typedef long long ll;
vector<PII> a(n);
for (int i = 0; i < n; i ++ ) a[i] = {efficiency[i], speed[i]};
sort(a.begin(), a.end(), greater<PII>());
priority_queue<int, vector<int>, greater<int>> heap;
ll sum = 0, ans = 0;
for (int i = 0; i < n; i ++ ) {
heap.push(a[i].second);
sum += a[i].second;
while (heap.size() > k) {
sum -= heap.top();
heap.pop();
}
ans = max(ans, sum * (ll)a[i].first);
}
return ans % mod;
}
};
细节
堆的参考资料
sort的参考资料
// 小顶堆，最小的数在队头，对应升序队列
priority_queue <int,vector<int>,greater<int> > q;
// 大顶堆，最大的数在队头，对应降序队列
priority_queue <int,vector<int>,less<int> >q;
// 升序排序
sort(begin,end,less<data-type>());
// 降序排序
sort(begin,end,greater<data-type>()).
版权声明：本文为博主作者：tsrigo原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/weixin_45574854/article/details/137093242
