单调队列与dp的关系

单调队列的介绍

顾名思义，单调队列就是指递增或者递减的队列，经过维护之后，让队列元素的第一个始终是范围内的最大或者最小值

其实现方法很多，可以开一个队列queue，或者直接在数组里用head和tail下标来完成

 1 void find_min()//求最小值的单调队列
 2 {
 3     int head = 0, tail = -1;
 4     for (int i = 0; i < n; i++)
 5     {
 6         if (head<=tail&&p[head] + k <= i) head++;//队列有元素，并且超出范围了，k是单调队列是多少个元素里最大，如果超出了这个值，那么队首元素就可以舍弃
 7         while (head <= tail && a[p[tail] ]>= a[i]) tail--;//队列有元素，要加入的值比队尾元素小，那么队尾元素就没有存在的意义了，因为我们要求的是最小值
 8         p[++tail] = i;//把要加入的值的坐标加入p[]，p是记录下标的
 9         if (i + 1 >= k) cout << a[p[head]] << " ";//满足长度之后，输出才有意义
10     }
11 }
12 void find_max()
13 {
14     int head = 0, tail = -1;
15     for (int i = 0; i < n; i++)
16     {
17         if (head <= tail && p[head] + k <= i) head++;
18         while (head <= tail && a[p[tail]] <= a[i]) tail--;
19         p[++tail] = i;
20         if (i + 1 >= k) cout << a[p[head]] << " ";
21     }
22 }

--------------------------------------------------------------------------------------------------------------------------------

单调队列和dp的关系

dp有的时候要求遍历某些前面的dp值来求出目前的dp值

如洛谷P3572 PTA-Little Bird

很容易看出转移方程

dp[j]=(前面范围内dp值最小的)+1/+0；

我们只需判断前面范围内哪个值dp最小，在dp值相同的情况下让高度最高

 1 #include <iostream>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 const long long int MAX = 2000010;
 6 long long int a[MAX];
 7 long long int p[MAX];
 8 long long int n;
 9 long long int dp[MAX];
10 deque<long long int>qq;
11 int main()
12 {
13     ios::sync_with_stdio(false);
14     cin.tie(0);
15     cout.tie(0);
16     long long int q,d;
17     cin >> n;
18     for (long long int i = 1; i <=n; i++)
19     {
20         cin >> a[i];
21     }
22     cin >> q;
23     while (q--)
24     {
25         cin >> d;
26         
27         qq.clear();
28        
29         qq.push_back(1);
30         for (long long int i = 2; i <= n; i++)
31         {
32             while (!qq.empty() && i - qq.front() > d) qq.pop_front();
33             if (a[qq.front()] > a[i]) dp[i] = dp[qq.front()];
34             else dp[i] = dp[qq.front()] + 1;
35             while (!qq.empty() && (dp[qq.back()] > dp[i] || (dp[qq.back()] == dp[i] && a[qq.back()] <= a[i]))) qq.pop_back();
36             qq.push_back(i);
37         }
38         cout << dp[n] << endl;
39     }
40     return 0;
41 }

总之，单调队列起到的是一个快捷找范围内最大最小的作用，适合数据较大的时候使用