绿色通道——单调队列加二分加dp——修建草坪——单调队列+dp——理想的正方西——二维单调队列

绿色通道

思路：
在烽火传递的基础上多一层二分，二分的判断的时候就用单调队列优化dp

代码：

#include 
using namespace std;
const int N = 5e4+10;
int w[N];
int n,m;
int q[N],f[N];
bool check(int limit){
    int hh =  0,tt = 0;
    for(int i = 1;i<=n;i++){
        if(q[hh]<i-limit-1) hh++;
        f[i] = f[q[hh]] + w[i];
        while(hh<=tt&&f[q[tt]]>= f[i]) tt--;
        q[++tt] = i;
    }
    int res = 1e9;
    for(int i = n-limit;i<=n;i++){
        res = min(res,f[i]);
    }
    return res<=m;
}
int main() {
    cin>>n>>m;
    for(int i = 1;i<=n;i++) cin>>w[i];
    int l = 0,r = n;
    while (l<r) {
        int mid = (l+r)>>1;
        if(check(mid)) r = mid;
        else l = mid+1;
    }

    cout<<r;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

修建草坪

思路：
fi为前i个中选择效率最高的
fi = max(fj-1+si-sj) 0<=i-j<=m

思路：

#include 
using namespace std;
const int N = 1e5+10;
long long f[N];
int q[N];
int e[N];
long long s[N];
long long max(long long a,long long b){
    return a>b?a:b;
}

long long g(int i){
    return f[i-1]-s[i];
}
int main() {
    int n,m;
    cin>>n>>m;
    for(int i = 1;i<=n;i++) {
        scanf("%d", &e[i]);
        s[i] = s[i-1]+e[i];
    }
    int hh = 0,tt= 0;
    for(int i = 1;i<=n;i++){
        if(q[hh]<i-m) hh++;
        f[i] = max(f[i-1],g(q[hh])+s[i]);
        while(hh<=tt&&g(q[tt])<=g(i)) tt--;
        q[++tt] = i;
    }
    cout<<f[n];
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

理想的正方形

思路：
求二维的最大值和最小值，阔以先把每一行的最大值求出来算到行末，再求每一列的最大值，这样在2n的时间里处理了每一个矩阵的最值。
单调队列阔以更加优化（√）

代码：

#include 
using namespace std;
const int N = 1e3+10;
int w[N][N];
int res_min[N][N];
int res_max[N][N];
int n,m,k;
int q[N];

void get_min(int a[],int b[],int tot){
    int hh = 0,tt = -1;
    for(int i = 1;i<=tot;i++){
        if(hh<=tt&&q[hh]<=i-k) hh++;
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
        q[++tt] = i;
        b[i] = a[q[hh]];
    }
}
void get_max(int a[],int b[],int tot){
    int hh = 0,tt = -1;
    for(int i = 1;i<=tot;i++){
        if(hh<=tt&&q[hh]<=i-k) hh++;
        while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
        q[++tt] = i;
        b[i] = a[q[hh]];
    }
}


int main() {
    cin>>n>>m>>k;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            scanf("%d",&w[i][j]);
        }
    }
    for(int i = 1;i<=n;i++){
        get_min(w[i],res_min[i],m);
        get_max(w[i],res_max[i],m);
    }

    int res = 1e9;

    int a[N],b[N],c[N];
    for(int i = k;i<=m;i++){
        for(int j = 1;j<=n;j++) a[j] = res_min[j][i];
        get_min(a,b,n);
        
        for(int j = 1;j<=n;j++) a[j] = res_max[j][i];
        get_max(a,c,n);
        
        for(int j = k;j<=n;j++)
            res = min(res,c[j]-b[j]);
    }

    cout<<res;
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60