首页 / 算法 / 【算法进阶指南】双端队列 DP+思维
【算法进阶指南】双端队列 DP+思维
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【算法进阶指南】双端队列 DP+思维，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2143字，纯文字阅读大概需要4分钟。
内容图文
题意
Sherry现在碰到了一个棘手的问题，有Ｎ个整数需要排序。Sherry手头能用的工具就是若干个双端队列。
她需要依次处理这N个数，对于每个数，Sherry能做以下两件事：
-
新建一个双端队列，并将当前数作为这个队列中的唯一的数；
-
将当前数放入已有的队列的头之前或者尾之后。
对所有的数处理完成之后，Sherry将这些队列排序后就可以得到一个非降的序列。
思路
反着考虑，我们先将所有的数字排好序，然后尽可能少的分成连续的几段，使得每段都可以出现在一个双端队列中。
分析一下可以知道，一个双端队列中的数字从头到尾的下标一定是先递减再递增，或者直接递增，或者直接递减。
注意多个数字相同时，可以对他们的下标任意排序。
首先处理出每个数字出现的最小下标和最大下标，按照数字大小排序之后进行DP。
\(dp[i][0]\) 表示以第 \(i\) 个数字是升序的方式出现在队列中需要的最小的队列数。
\(dp[i][1]\) 表示以第 \(i\) 个数字是倒序的方式出现在队列中需要的最小的队列数。
初始化\(dp[1][1] = dp[1][0] = 1\)
具体转移看代码
代码
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <vector>
#define pb push_back
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 3e5 + 10;
const int mod = 1e9 + 7;
using namespace std;
vector<int> vec;
map<int, int> minn, maxn;
int dp[N][2];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
vec.pb(x);
maxn[x] = i;
if (!minn[x])
minn[x] = i;
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
memset(dp, inf, sizeof(dp));
dp[0][0] = dp[0][1] = 1;
for (int i = 1; i < vec.size(); i++) { //遇到降序时dp值才增加
dp[i][0] = min(dp[i][0], dp[i - 1][1]);//在上次递减，这次递增，dp值不变
if (minn[vec[i]] > maxn[vec[i - 1]]) {
dp[i][0] = min(dp[i][0], dp[i - 1][0]);//在上次递增的基础上递增
} else {
dp[i][0] = min(dp[i][0], dp[i - 1][0] + 1);//上次递增，这次先递减再递增，dp值+1
}
dp[i][1] = min(dp[i][1], dp[i - 1][0] + 1);//在上次递增，这次递减，dp值+1
if (maxn[vec[i]] < minn[vec[i - 1]]) {//在上次递减的基础上再递减，dp值不变
dp[i][1] = min(dp[i - 1][1], dp[i][1]);
} else {
dp[i][1] = min(dp[i][1], dp[i - 1][1] + 1);//上次递减，这次先递增再递减，dp值+1
}
}
printf("%d\n", min(dp[vec.size() - 1][0], dp[vec.size() - 1][1]));
return 0;
}
内容总结
以上是互联网集市为您收集整理的【算法进阶指南】双端队列 DP+思维全部内容，希望文章能够帮你解决【算法进阶指南】双端队列 DP+思维所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。