单调队列理解

对于单调队列，我们这样子来定义： 
1、维护区间最值 
2、去除冗杂状态 如上题，区间中的两个元素a[i],a[j]（假设现在再求最大值） 若 j>i且a[j]>=a[i] ，a[j]比a[i]还大而且还在后面（目前a[j]留在队列肯定比a[i]有用，因为你是往后推， 认真想！ 重点） 
3、保持队列单调，最大值是单调递减序列，最小值反之 
4、最优选择在队首

大致过程： 
1、维护队首（对于上题就是如果你已经是当前的m个之前那你就可以被删了,head++） 
2、在队尾插入（每插入一个就要从队尾开始往前去除冗杂状态） 

设A(x),B(x),C(x),D(x)为仅关于x的一元函数

单调队列DP

DP转移方程需要满足的条件：

dp[i]=A(i)+B(j)中的最小/大值 (i-k<=j<i,k为常数)

例子：

dp[i]=dp[j]+(i-j)*w // 选自hdu3401
A(i)=i*w
B(j)=dp[j]-j*w

分析：

维护B(j)的最大合法值进行转移即可

 

例题:输入一个长度为n的整数序列，从中找出一段不超过M的连续子序列，使得整个序列的和最大。 

分析:前缀和 ans=sum[i]-min(sum[i-1],sum[i-2].....sum[i-m])

1，-3,5,1，-2,3
当m=4时，S=5+1-2+3=7
当m=2或m=3时，S=5+1=6  

原STL代码:

#include <iostream>
#include <list>
#include <cstdio>
using namespace std;

int n, m;
long long s[300005];
// 前缀和

list<int> queue;
// 链表做单调队列

int main() {
    cin >> n >> m;
    s[0] = 0;
    for (int i=1; i<=n; i++) {
        cin >> s[i];
        s[i] += s[i-1];
    }
    long long maxx = 0;
    for (int i=1; i<=n; i++) {
        while (!queue.empty() and s[queue.front()] > s[i])
            queue.pop_front();
        // 保持单调性
        queue.push_front(i);
        // 插入当前数据
        while (!queue.empty() and i-m > queue.back())
            queue.pop_back();
        // 维护区间大小，使i-m >= queue.back()
        if (i > 1)
            maxx = max(maxx, s[i] - s[queue.back()]);
        else
            maxx = max(maxx, s[i]);
        // 更新最值
    }
    cout << maxx << endl;
    return 0;
}

数组单调队列代码:

#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!
")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que;
const double EPS = 1.0e-8;
const double eps = 1.0e-8;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 300005;
const int  maxm = 300;
//next_permutation
#include<iostream>
#include<string>
using namespace std;
int n, m;
int a[maxn], ansmin[maxn], ansmax[maxn];
int q[maxn];
int dp[maxn];
int ans=0;
void getmin()
{
        int head = 1;
        int tail = 1;
        q[head] = q[head + 1] = 0;
        for (int i = 1; i <= n; i++)
        {
                while (head <= tail && a[q[tail]] >= a[i])
                {
                        tail--;
                }
                q[++tail] = i;
                while (head <= tail && q[head] < i - m)
                {
                        head++;
                }
                if (i == 1)
                {
                        ans=dp[1]=a[1];
                }
                else
                dp[i]=a[i]-a[q[head]],ans=max(ans,dp[i]);
        }
}
int main()
{
        cin >> n >> m;
        a[0]=0;
        for (int i = 1; i <= n; i++)
        {
                scanf("%d", &a[i]);
                a[i] += a[i - 1];
        }
        getmin();
        cout<<ans<<endl;
        return 0;
}