@RabbitHu 2017-08-27T01:28:12.000000Z 字数 5278 阅读 1730

单调栈、单调队列专题

笔记

51nod 1158 全是1的最大子矩阵 | 单调栈

给出1个M*N的矩阵M1，里面的元素只有0或1，找出M1的一个子矩阵M2，M2中的元素只有1，并且M2的面积是最大的。输出M2的面积。
Input
第1行:2个数m,n中间用空格分隔(2 <= m,n <= 500)
第2 - N + 1行：每行m个数，中间用空格分隔，均为0或1。
Output
输出最大全是1的子矩阵的面积。

枚举子矩阵的最下面一行，对每一位求向上的前缀和，枚举前缀和最小位，向左右延伸得到最大的以它为最小值的区间，区间宽度*这个最小值来更新答案。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 502;
int m, n, mp[N][N], sum[N], stk[N], top, toleft[N], toright[N], ans;
int main(){
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &mp[i][j]);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++)
            sum[j] = mp[i][j] ? sum[j] + 1 : 0;
        top = 0, stk[0] = 0;
        for(int j = 1; j <= m; j++){
            while(top && sum[stk[top]] >= sum[j]) top--;
            toleft[j] = stk[top];
            stk[++top] = j;
        }
        top = 0, stk[0] = m + 1;
        for(int j = m; j; j--){
            while(top && sum[stk[top]] >= sum[j]) top--;
            toright[j] = stk[top];
            stk[++top] = j;
        }
        for(int j = 1; j <= m; j++)
            ans = max(ans, sum[j] * (toright[j] - toleft[j] - 1));
    }
    printf("%d\n", ans);
    return 0;
}

51nod 1255 字典序最小的序列 | 贪心单调栈

给出一个由a-z组成的字符串S，求他的一个子序列，满足如下条件：

1、包含字符串中所有出现过的字符各1个。
2、是所有满足条件1的串中，字典序最小的。

例如：babbdcc，出现过的字符为：abcd，而包含abcd的所有子序列中，字典序最小的为abdc。
Input
输入1行字符串S，所有字符均为小写，字符串的长度为L。(1 <= L <= 100000)。
Output
输出包含S中所有出现过的字符，每个字符各1个，并且字典序最小的S的子序列。

维护一个栈，从左往右，如果栈顶元素比当前元素大，且以后还会出现，则弹出。

注意栈中元素不能重复，且根本不打算放进去的元素是不能用来把别的元素弹出去的。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 100005;
char s[N], stk[28];
int n, last[128], top;
bool vis[128];
int main(){
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(int i = n; i; i--)
        if(!last[s[i]]) last[s[i]] = i;
    for(int i = 1; i <= n; i++){
        if(vis[s[i]]) continue;
        while(top && stk[top] > s[i] && last[stk[top]] > i)
            vis[stk[top--]] = 0;
        vis[stk[++top] = s[i]] = 1;
    }
    for(int i = 1; i <= top; i++)
        printf("%c", stk[i]);
    puts("");
    return 0;
}

51nod 1423 最大二“货” | 单调栈

白克喜欢找一个序列中的次大值。对于一个所有数字都不同的序列 $x_1, x_2, ..., x_k (k > 1)$ ，他的次大值是最大的 xj ,并且满足 $xj ≠ \max^{k}_{i=1} xi$
对于一个所有数字都不同的序列 $x1, x2, ..., xk (k > 1)$ ，他的幸运数字是最大值和次大值的异或值(Xor)。
现在有一个序列 $s_1, s_2, ..., s_n (n > 1)$ 。 $s[l,r]$ 表示子段 $s_l, s_{l+1}, ..., s_r$ 。你的任务是找出所有子段的最大幸运数字。
注意，序列s中的所有数字都是不同的。

从左到右扫一遍，维护单调递减栈，要把一个新元素放进去的时候，它在栈中的前一个元素可以作为区间最大值，新元素作为区间次大值；但是从左到右扫一遍只能求最大值在左、次大值在右的情况，从右到左再扫一遍，就能求出所有情况了。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
int read(){
    char c; 
    while((c = getchar()) < '0' || c > '9');
    int ret = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
        ret = ret * 10 + c - '0';
    return ret;
}
const int N = 100005;
int n, a[N], stk[N], top, ans;
int main(){
    while(~scanf("%d", &n)){
        for(int i = 1; i <= n; i++)
            a[i] = read();
        top = 0;
        for(int i = 1; i <= n; i++){
            while(top && stk[top] < a[i]) top--;
            ans = max(ans, stk[top] ^ a[i]);
            stk[++top] = a[i];
        }
        top = 0;
        for(int i = n; i; i--){
            while(top && stk[top] < a[i]) top--;
            ans = max(ans, stk[top] ^ a[i]);
            stk[++top] = a[i];
        }
        printf("%d\n", ans);
    }
    return 0;
}

51nod 1275 连续子段的差异 | 单调队列

给出一个包括N个元素的整数数组A，包括A本身在内，共有 (N+1)*N / 2个非空子段。例如：1 3 2的子段为{1} {3} {2} {1 3} {3 2} {1 3 2}。在这些子段中，如果最大值同最小值的差异不超过K，则认为这是一个合格的子段。给出数组A和K，求有多少符合条件的子段。例如：3 5 7 6 3，K = 2，符合条件的子段包括：{3} {5} {7} {6} {3} {3 5} {5 7} {7 6} {5 7 6}，共9个。
Input
第1行：2个数N, K（1 <= N <= 50000, 0 <= K <= 10^9)
第2 - N + 1行：每行1个数，对应数组的元素Ai(0 <= A[i] <= 10^9)
Output
输出符合条件的子段数量。

扫一遍，把每个元素丢进一个能求最大值最小值的队列里，如果最大值减最小值大于K了就从队列左边弹出元素。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 50005;
int n, k, ans, a[N], qmin[N], qmax[N], l, r, lmin, rmin, lmax, rmax;
int main(){
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    lmin = lmax = l = 1, rmin = rmax = 0;
    for(r = 1; r <= n; r++){
        while(lmin <= rmin && a[qmin[rmin]] >= a[r]) rmin--;
        qmin[++rmin] = r;
        while(lmax <= rmax && a[qmax[rmax]] <= a[r]) rmax--;
        qmax[++rmax] = r;
        while(a[qmax[lmax]] - a[qmin[lmin]] > k && lmin <= rmin && lmax <= rmax){
            if(qmin[lmin] == l) lmin++;
            if(qmax[lmax] == l) lmax++;
            l++;
        }
        ans += r - l + 1;
    }
    printf("%d\n", ans);
    return 0;
}

51nod 1086 多重背包 O(VN) 做法 | 单调队列

有 $n$ 种物品，每种物品的数量为 $c[i]$ 。从中任选若干件放在容量为 $m$ 的背包里，每种物品的体积为 $w[i]$ （为整数），与之相对应的价值为 $p[i]$ （为整数）。求背包能够容纳的最大价值。

Input
第1行，2个整数， $n$ 和 $m$ 中间用空格隔开。 $m$ 为物品的种类， $m$ 为背包的容量。(1 <= $n$ <= 100，1 <= $m$ <= 50000)
第2 - $n$ + 1行，每行3个整数， $w[i]$ ， $p[i]$ 和 $c[i]$ 分别是物品体积、价值和数量。(1 <= $w[i], p[i]$ <= 10000， 1 <= $c[i]$ <= 200)

Output
输出可以容纳的最大价值。

多重背包。

首先写出朴素的状态转移方程（ $dp[i][j]$ 表示前 $i$ 个物品、总体积为 $j$ ）：

$dp[i][j] = \max_{k = 0}^{c[i]} dp[i - 1][j - k * w[i]] + k * p[i]$

直接这样算的复杂度最差可达 $O(nm^2)$ （ $c[i]$ 极大、 $w[i]$ 极小时）。

那么我们如何优化呢？考虑 $w[i]$ 为 $x$ 、 $j$ 为 $4x, 5x, 6x$ 、 $c[i]$ 为 $2$ 时的计算过程：

$dp[i][4x] = max(dp[i-1][4x], dp[i-1][3x] + p[i], dp[i-1][2x] + 2p[i])$
$dp[i][5x] = max(dp[i-1][5x], dp[i-1][4x] + p[i], dp[i-1][3x] + 2p[i])$
$dp[i][6x] = max(dp[i-1][6x], dp[i-1][5x] + p[i], dp[i-1][4x] + 2p[i])$

提出一些 $p[i]$ ，将以上三式整理一下：

$dp[i][4x] = max(dp[i-1][4x], dp[i-1][3x] + p[i], dp[i-1][2x] + 2p[i])$
$dp[i][5x] = max(dp[i-1][5x] - p[i], dp[i-1][4x], dp[i-1][3x]) + p[i]$
$dp[i][6x] = max(dp[i-1][6x] - 2p[i], dp[i-1][5x] - p[i], dp[i-1][4x]) + 2p[i]$

可以发现，以上三式的计算中有许多重复的地方。

那么如何消除重复，达到优化呢？观察原始方程：

$dp[i][j] = \max_{k = 0}^{c[i]} dp[i - 1][j - k * w[i]] + k * p[i]$

设 $a = j \% w[i], b = j / w[i]$ ，则上式等价于：

$dp[i][a + b * w[i]] = \max_{k = b - c[i]}^{b} dp[i - 1][a + k * w[i]] - k * p[i] + b * p[i]$

那么在每个i循环中，可以把所有的j按a分成w[i]组，每组新建一个队列，枚举b，每次把 $dp[i - 1][a + k * w[i]] - k * p[i]$ 放进队列，并保持队列长度不超过c[i]，用O(1)求出队列中最大值、从最大值转移即可。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 103, M = 50003;
int n, m, w[N], p[N], c[N], ans;
//w[i]: 体积; p[i]: 价值; c[i]: 数量
int dp[M], qa[M], qb[M], la, lb, ra, rb;
//qa: 正常队列; qb: 用来求最大值的辅助队列
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d%d%d", &w[i], &p[i], &c[i]);
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < w[i]; j++){
            la = lb = 0, ra = rb = -1;//清空队列
            for(int k = 0; j + k * w[i] <= m; k++){
                if(ra - la + 1 > c[i])//如果队列中元素个数超过限制
                    if(qb[lb] == qa[la++]) lb++; //从队首弹出
                int x = dp[j + k * w[i]] - k * p[i];
                qa[++ra] = x;
                while(rb >= lb && qb[rb] < x) rb--;
                qb[++rb] = x;
                dp[j + k * w[i]] = qb[lb] + k * p[i];
                ans = max(ans, dp[j + k * w[i]]);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}