当前位置：网站首页>Monotonic queue optimization DP

Monotonic queue optimization DP

2022-07-23 19:25:00 【lovesickman】

Monotonic queue optimization DP

1089. Beacon transmission

I wrote the question a year and a half ago , A very simple state transition equation , I won't think about it now .

Be good at fine tuning state definitions .

At first I thought $f [i]$ Express $1\sim i$ Minimum cost of , No definition The first $i$ The state of beacon towers .

Will be divided into lit or not lit .

If it is lit ： $\le j<i$ ;

If not lit ： The first $i$ Beacon towers may be the first location of the empty section , Second position , Then it affects the elements behind .

~~And then I won't~~

I saw y The total , Direct definition $f [i]$ Express $1\sim i$ Minimum cost of , And Light The first $i$ A beacon tower .

Then the state transition equation is directly ： $\le j<i$ ;

The enumeration answer is ： $\sim n]_{min}$

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=2e5+10;

int f[N],a[N],q[N];
int n,m,hh=0,tt=-1;

int main()
{
    
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    memset(f,0x3f,sizeof f);
    f[0] = 0;
    //f[i]=min(f[j]+w[i]), i-m<=j<i;
    for(int i=1;i<=n;i++){
    
        for(int j=max(0,i-m);j<i;j++){
    
            f[i] = min(f[i],f[j]+a[i]);
        }
    } 
    int res = 0x3f3f3f3f;
    for(int i=n;i>=n-m+1;i--){
    
        res = min(res,f[i]);
    }
    cout<<res;
    return 0;
}

Optimize the minimum value of fixed interval with monotone queue .

There is a very big pit here , I haven't noticed before

        if(hh<=tt && i-q[hh]+1>m+1)
            hh++; (1)
        f[i] = f[q[hh]] + a[i]; (2)
        while(hh<=tt && f[i] <= f[q[tt]]) (3)
            tt--;
        q[++tt] = i; (4)

Consider the order of these four sentences . Experiments have proved that this order will not wa

（3） Sentence indication $a [i]$ Intend to enter the monotonous queue , therefore （3） Before , The sliding window is $[i - m, i - 1]$

（4） sentence , It is usually the last sentence .（1） Sentences in the sliding window board can be compared with （3） Sentence Exchange .

So the problem is （2） Where is the sentence usually placed .

The left side of the sliding window is bounded by （1） Sentence definition . There are two ways of understanding ：

$i - i Corresponding left endpoint + 1 Corresponding interval length$ , If the interval length ratio $The requirements are big$ Out of the team .
q[hh] < i - m ; The head of the team is in a better position than i The corresponding leftmost position is smaller , It shows that the team leader is outside the window .

problem ： If the sliding window is [i-m , i - k] So how to write ？

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=2e5+10;

int f[N],a[N],q[N];
int n,m,hh=0,tt=-1;

int main()
{
    
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    memset(f,0x3f,sizeof f);
    f[0] = 0;
    q[++tt] = 0;
    //f[i]=min(f[j]+w[i]), i-m<=j<i;
    for(int i=1;i<=n;i++){
    
        if(hh<=tt && i-q[hh]+1>m+1)
            hh++;
        f[i] = f[q[hh]] + a[i];
        while(hh<=tt && f[i] <= f[q[tt]])
            tt--;
        q[++tt] = i;
    } 
    int res = 0x3f3f3f3f;
    for(int i=n;i>=n-m+1;i--){
    
        res = min(res,f[i]);
    }
    cout<<res;
    return 0;
}

1090. Green channel

It's just the beacon relay plus a two-point answer , But something strange happened again . The left boundary of the binary answer needs +1 To become the right answer . Vomit .

/* A: 10min B: 20min C: 30min D: 40min */ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <assert.h>
#include <sstream>
#define pb push_back 
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){
    for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){
    j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){
    for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){
    for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
    
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {
    if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}

typedef pair<long long ,long long >PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=5e4+10,M=1e9+7;

int n,m,a[N];
int f[N];
int q[N],hh,tt=-1;
bool check(int mid){
    
    fo(i,1,n)f[i] = 0x3f3f3f3f;
    hh = 0,tt = 0;
    f[0] = 0;
    for(int i=1;i<=n;i++){
      
        if(hh<=tt && q[hh] < i-mid-1)
            hh++;
        f[i] = f[q[hh]] + a[i];
        while(hh<=tt && f[i] <= f[q[tt]])
            tt--;
        q[++tt] = i;
    }
    for(int i=n-mid;i<=n;i++){
    
        if(f[i]<=m)return 1;
    }
    return 0;
}

void solve(){
    
    cin>>n>>m;
    fo(i,1,n)cin>>a[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<<endl;
}

int main(){
    
    solve();
    return 0;
}

Title Description

In fantasy country , Cheruno is the ice goblin known as a fool .

One day , Cheruno is playing frozen frog again , It's freezing frogs with ice . But this frog is much smarter than before , I ran across the river before cheruno came . So qiluno decided to go to the river bank to chase the frog .

A stream can be seen as a row of cells, numbered in turn as $0$ To $N$ , Cheruno can only move from a small number to a large number . And cheruno moves in a special way , When she's in the grid $i$ when , She only moves to the interval $[i + L, i + R]$ Any space in . You ask why she's moving like this , It's not easy , Because she's a fool .

Each grid has a freezing index $A_i$ , The number is $0$ The lattice freezing index of is $0$ . When cheruno stays in that grid, he can get the freezing index of that grid $A_i$ . Cheruno hopes to be on the other side , Get the maximum freezing index , So she can teach the frog a lesson .

But because she was so stupid , So she decided to ask you to help her decide how to move forward .

At the beginning of the , Cheruno is numbering $0$ On the grid , As long as her next position number is greater than $N$ Even if we get to the other side .

Input format

The first line is three positive integers $N, L, R$ .

The second line is $N + 1$ It's an integer , The first $i$ The number means the number is $i - 1$ The freezing index of the lattice $A_{i-1}$ .

Output format

An integer , Is the maximum freezing index .

Examples #1

The sample input #1

5 2 3
0 12 3 11 7 -2

Sample output #1

Tips

about $60\%$ The data of , $\le 10^4$ .

about $100\%$ The data of , $\le 2\times 10^5$ ,$-10^3 \le A_i\le 10^3 $,$1 \le L \le R \le N $. The data guarantees that the final answer will not exceed $2^{31}-1$ .

A problem of great torture .

For details, see the first title .

Learn to deal with the right endpoint and i Sliding windows with intervals

$\ (i−R≤j≤i−L)$

/* A: 10min B: 20min C: 30min D: 40min */ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <assert.h>
#include <sstream>
#define pb push_back 
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){
    for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){
    j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){
    for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){
    for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
    
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {
    if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}

typedef pair<long long ,long long >PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=3e5+10,M=1e9+7;

int n,l,r;
ll a[N],f[N];
int q[N],hh,tt;
void solve(){
    
    cin>>n>>l>>r;
    fo(i,0,n)cin>>a[i];
	memset(f,0xcf,sizeof f);
	f[0] = 0;
	// f[i] Jump to the i The maximum value that can be obtained by lattice 
    ll ans = -0x3f3f3f3f;
    for(int i=l;i<=n;i++){
    	
    
    	while(hh<=tt && f[i-l] >= f[q[tt]])
    		tt--;
    	q[++tt] = i-l;
    	
    	if(hh<=tt && q[hh] < i-r)
    		hh++;
    	f[i] = f[q[hh]] + a[i];
    	if(i+r>n)
    		ans = max(ans,f[i]);
    }
    cout<<ans;
}

int main(){
    
    solve();
    return 0;
}