#0.0 Pre knowledge

This paper is about Monotonic queue optimization dp, Please make sure you have mastered the following knowledge :




#1.0 Brief introduction

#1.1 The essence & Scope of application

Using monotonic queue optimization dp, The essence is to use monotonicity , In time Eliminate impossible decisions , To maintain the effectiveness and order of the candidate set .

Monotone queue is very suitable for optimizing the range of decision values On 、 The lower bounds are monotonic , Each decision is in the candidate set Insert or delete to one more time

#1.2 Applicable equation & Conditions

Most of the state transition equations that can use monotone queues can be reduced to the following form :

\[\begin{aligned}
f_i=\min_{L(i)\leq j\leq R(i)}\{f_j+val(i,j)\}
\end{aligned}
\]

among \(L(i)\) and \(R(i)\) It's two about \(i\) The primary function of , Limit \(j\) Value range of ,\(val(i,j)\) It's a story about \(i,j\) The polynomial function of .

Conditions :

  • polynomial \(val(i,j)\) Each item of is only related to \(i\) and \(j\) One of them is about

Go straight to the example

#2.0 Example explanation

#2.1 P3572 [POI2014]PTA-Little Bird

#2.1.1 About the topic

The translation of the topic is very important :

The bird starts to jump from the first tree (On top of the first one, there is a little bird who ...)

#2.1.2 Simple algorithm

I believe it is not difficult to write the state transfer equation of this problem :

\[\begin{aligned}
f_i = \min_{i-k\leq j<i}\{f_j+[a_j\leq a_i]\}
\end{aligned}
\]

Pseudo code

\[\begin{aligned}
&f_1 \leftarrow 0\\
&\text{For }i \leftarrow2\text{ to }n\\
&\quad\quad \text{do For }j\leftarrow i-k\text{ to }i-1\text{ by }1\text{ do}\\
&\quad\quad\quad\quad f_i\leftarrow\min\{f_i,f_j+(a_j<=a_i)\ ?\ 1:0\}\\
&\quad\quad \text{End}
\end{aligned}
\]

#2.1.3 Monotonicity analysis

Observe \(j\) Value range of :

\[\begin{aligned}
i-k\leq j<i
\end{aligned}
\]

When \(i\) increase \(1\) when ,\(j\) The upper and lower bounds of the range of increase \(1\), It means only one new decision at a time \(f_i\) Join the candidate set , One old decision at most \(f_{i-k}\) Excluded candidate sets , obviously , The subscript in the candidate set should be Monotone increasing Of , There is no need to pay special attention to this

obviously , Every decision we want to get \(f_j\) It should be in the candidate set The smallest , in other words , If there's a decision \(f_p,f_q,p<q<i,f_p>f_q\) , obviously \(f_q\) Than \(f_p\) better , because \(f_q\) Than \(f_p\) It lasts longer in the candidate set , And contribute to \(f\) Less valuable , that \(f_p\) Obviously useless , You can just give up , therefore , We should maintain the candidate set \(f_j\) Monotone increasing

Then if \(f_p=f_q\) Well ? Obviously we choose Higher , namely \(a\) Bigger, better

  • Because of the assumption \(a_p<a_q\)

    • If \(a_p<a_q\leq a_i\) , You need to add one to both , So the contributions of the two are the same , and \(p<q\), It means \(q\) It can be kept in the queue longer , So choose \(p\) Obviously, you can just throw it away
    • if \(a_p\leq a_i<a_q\), Obvious choice \(a_q\) The result is better
    • if \(a_i<a_p<a_q\), Whatever you choose \(p\) still \(q\) The results are the same , and \(p<q\), It means \(q\) It can be kept in the queue longer , So choose \(p\) Obviously, you can just throw it away
  • if \(a_p=a_q\), Obviously anyway \(p\) And \(q\) All the contributions are the same , \(p<q\), It means \(q\) It can be kept in the queue longer , So choose \(p\) Obviously, you can just throw it away
  • however , If \(a_p>a_q\),\(a_q\) still It may be the best decision for the later transfer ( When \(p\) When it's out of range ,\(q\) It's still possible to be in scope and optimal )

So we should maintain the When \(f_j\) When equal , \(a_j\) Monotonic decline

In conclusion , The choice of decision-making is monotonous , We can maintain a monotonic queue as follows

  • \(f_j\) Monotone increasing
  • When \(f_j\) When equal , \(a_j\) Monotonic decline

#2.1.4 Code code

const int N = 1000010;
const int INF = 0x3fffffff; int n,k,t,a[N],f[N],q[N]; int main(){
scanf("%d",&n);
for (int i = 1;i <= n;i ++)
scanf("%d",&a[i]);
scanf("%d",&t);
while (t --){
scanf("%d",&k);
int frt = 0,tal = -1; // Clear queue
q[++ tal] = 1; // Join the initial candidate decision
for (int i = 2;i <= n;i ++){
while (frt <= tal && q[frt] + k < i)
frt ++; // Remove the out of range
f[i] = f[q[frt]] + (a[q[frt]] <= a[i]); // Transfer
while (frt <= tal && ((f[q[tal]] > f[i]) || (f[q[tal]] == f[i] && a[q[tal]] <= a[i])))
tal --; // Maintaining monotony from the end of the team , Team new decisions
q[++ tal] = i;
}
cout << f[n] << endl;
}
return 0;
}

#2.2 P3089 [USACO13NOV]Pogo-Cow S

#2.2.1 Simple algorithm

First , It's not hard to imagine. , The biggest score must start at one end , Jump all the way in one direction , So we need one up here sort() Sort the data , And because there are two directions , So we have to do it twice DP

set up \(f_{i,j}\) The last step is from \(j\) To \(i\) My biggest score

It's not hard to write the transfer equation :

\[\begin{aligned}
f_{i,j} = \max_{k<j<i\and x_j-x_k\leq x_i-x_j}\{f_{j,k}\}+p_i
\end{aligned}
\]

Code :

const int N = 1010;
const int INF = 0x3fffffff; struct Node{
int p;
int a;
};
Node s[N]; int n,sum[N],f[N][N],ans; int cmp(const Node x,const Node y){
return x.p < y.p;
} int main(){
scanf("%d",&n);
for (int i = 1;i <= n;i ++)
scanf("%d%d",&s[i].p,&s[i].a);
sort(s + 1,s + n + 1,cmp);
for (int i = 1;i <= n;i ++)
f[i][i] = s[i].a;
for (int i = 1;i <= n;i ++)
for (int j = 1;j < i;j ++){
for (int k = 1;k <= j;k ++)
if (s[j].p - s[k].p <= s[i].p - s[j].p)
f[i][j] = max(f[i][j],f[j][k] + s[i].a);
ans = max(ans,f[i][j]);
}
mset(f,0);
for (int i = 1;i <= n;i ++)
f[i][i] = s[i].a;
for (int i = n;i >= 1;i --)
for (int j = n;j > i;j --){
for (int k = n;k >= j;k --)
if (s[k].p - s[j].p <= s[j].p - s[i].p)
f[i][j] = max(f[i][j],f[j][k] + s[i].a);
ans = max(ans,f[i][j]);
}
cout << ans;
return 0;
}

#2.2.2 Monotonicity analysis

Look at the transfer equation

\[\begin{aligned}
f_{i,j} = \boxed{\max_{k<j<i\and x_j-x_k\leq x_i-x_j}\{f_{j,k}\}}+p_i
\end{aligned}
\]

The framing part is for \(f_{j,k}\) The maximum of , Consider the possibility of monotonic optimization , It's not hard to find out , The sequence \(\{x_k\}\) It is a monotonous sequence of numbers , When \(j\) Constant time ,\(i\) Add a , The transfer equation is

\[\begin{aligned}
f_{i+1,j} = \max_{k<j<i+1\and x_j-x_k\leq x_{i+1}-x_j}\{f_{j,k}\}+p_{i+1}
\end{aligned}
\]

\(k\) Value range of \(1\leq k<j\) There is no change , It's just satisfaction \(x_j-x_k\leq x_{i+1}-x_j\) Of \(k\) Maybe more , and , Obviously if \(x_j-x_p\nleq x_{i+1}-x_j\), about \(q<p\) There must be \(x_j-x_q\nleq x_{i+1}-x_j\), This is equivalent to the direct existence of a monotonous queue that does not need to be out of the team , Because the sequence of numbers \(\{x_k\}\) It is a monotonous sequence of numbers , We just need to record the current satisfaction \(x_j-x_k\leq x_{i+1}-x_j\) The smallest \(k\), Save the maximum value in the range , Next time from \(k+1\) Just start updating , Be careful , Because this is \(i\) Add a ,\(j\) Unchanging situation , So will \(j\) The changes are put in the outer loop ,\(i\) In the inner layer

#2.2.3 Code code

const int N = 1010;
const int INF = 0x3fffffff; struct Node{
int p;
int a;
};
Node s[N]; int n,sum[N],f[N][N]; int cmp(const Node x,const Node y){
return x.p < y.p;
} int main(){
scanf("%d",&n);
for (int i = 1;i <= n;i ++)
scanf("%d%d",&s[i].p,&s[i].a);
sort(s + 1,s + n + 1,cmp);
int ans = 0;
for (int j = 1;j < n;j ++){
int k = j;
f[j][j] = s[j].a;
for (int i = j + 1;i <= n;i ++){
f[i][j] = f[i - 1][j] - s[i - 1].a; // Obviously, the value of the last transfer must be the maximum value of the last interval
while (k && s[j].p - s[k].p <= s[i].p - s[j].p)
f[i][j] = max(f[i][j],f[j][k --]);
f[i][j] += s[i].a;
ans = max(ans,f[i][j]);
}
}
mset(f,0);
for (int j = n;j > 1;j --){ // Don't forget to ask twice , In reverse order
int k = j;
f[j][j] = s[j].a;
for (int i = j - 1;i >= 1;i --){
f[i][j] = f[i + 1][j] - s[i + 1].a;
while (k <= n && s[k].p - s[j].p <= s[j].p - s[i].p)
f[i][j] = max(f[i][j],f[j][k ++]);
f[i][j] += s[i].a;
ans = max(ans,f[i][j]);
}
}
cout << ans;
return 0;
}

#3.0 Monotone queue optimization multiple knapsack

#3.1 analysis

Let's first consider the simplest solution to the multiple knapsack problem

The equation of state transfer is

\[\begin{aligned}
f_j=\max_{1\leq cnt \leq c_i}\{f_{j-cnt\times v_i}+cnt\times W_i\}
\end{aligned}
\]

Pseudo code :

\[\begin{aligned}
&\text{For }i\leftarrow1\text{ to }n\\
&\quad\quad \text{do For }cnt\leftarrow 1\text{ to }c_i\\
&\quad\quad\quad\quad \text{do For }j\leftarrow M\text{ to }cnt\times v_i\text{ by }-1\text{ do}\\
&\quad\quad\quad\quad\quad\quad f_{j}\leftarrow\max\{f_j,f_{j-cnt\times v_i}+cnt\times w_i\}\\
&\quad\quad\quad\quad\text{End}
\end{aligned}
\]

Let's take a look at being able to move to a state \(j\) The decision candidate set of , by \(\{j-cnt\times v_i|1\leq cnt\leq c_i\}\)

Let's take a look at how we can move to \(j-1\) The candidate set of , by \(\{j-cnt\times v_i-1|1\leq cnt\leq c_i\}\)

Obviously the two sets don't intersect , It's impossible to get from \(j\) The decision set of \(j-1\) The decision set of

that , We cycle from the innermost layer to the outer layer , Observe \(cnt\) Yes \(j\) The impact of decision sets on

When \(cnt\) Add a moment , state \(j-v_i\) The decision candidate set of is \(\{j-(cnt+1)\times v_i|1\leq cnt+1\leq c_i\}\)

Here's the picture :

obviously , If we take the State \(j\) Follow the mold \(v_i\) The remainder of \(u\) grouping , Make \(p\in[0,\lfloor\dfrac{M-u}{v_i}\rfloor]\), Reverse cycle , The decision candidate set of each group can be quickly derived , New state transfer equations :

\[\begin{aligned}
f_{u+p\times v_i}&=\max_{p-c_i\leq k\leq p-1}\{f_{u+k\times v_i}+(p-k)\times w_i\}\\
&=\max_{p-c_i\leq k\leq p-1}\{f_{u+k\times v_i}-k\times w_i+p\times w_i\}
\end{aligned}
\]

obviously , If we want the results to be as big as possible , You need to make decisions \(k\) Of \(f_{u+k\times v_i}-k\times w_i\) As big as possible

So when \(p\) For a while ,\(k\) The upper and lower bounds of are reduced by one , We need a \(k\) Monotonic decline ,\(f_{u+k\times v_i}-k\times w_i\) Monotonic decline The monotonous queue of , It can be maintained according to the basic operation of monotonic queue every time

#3.2 Code code

const int N = 100010;
const int INF = 0x3fffffff; int n,m;
int v[N],w[N],c[N];
int f[N],q[N]; inline int val(int i,int u,int k){
return f[u + k * v[i]] - k * w[i];
} int main(){
scanf("%d%d",&n,&m);
for (int i = 1;i <= n;i ++){
scanf("%d%d%d",&w[i],&v[i],&c[i]);
for (int u = 0;u < v[i];u ++){
int l = 0,r = -1;
int maxp = (m - u) / v[i];
for (int k = maxp - 1;k >= max(maxp - c[i],0);k --){
while (l <= r && val(i,u,q[r]) <= val(i,u,k))
r --;
q[++ r] = k;
}
for (int p = maxp;p >= 0;p --){
while (l <= r && q[l] > p - 1)
l ++;
if (l <= r)
f[u + p * v[i]] = max(f[u + p * v[i]],val(i,u,q[l]) + p * w[i]);
if (p - c[i] - 1 >= 0){
while (l <= r && val(i,u,q[r]) <= val(i,u,p - c[i] - 1))
r --;
q[++ r] = p - c[i] - 1;
}
}
}
}
int ans = 0;
for (int i = 0;i <= m;i ++)
ans = max(ans,f[i]);
cout << ans;
return 0;
}

[DP elementary analysis ] linear DP preliminary - 2 - More articles on monotonic queue optimization

  1. [bzoj2806][Ctsc2012]Cheat( Postfix automaton (SAM)+ Two points answer + Monotonic queue optimization dp)

    Just be lazy bzoj The web content of ctrlcv Over here. 2806: [Ctsc2012]Cheat Time Limit: 20 Sec  Memory Limit: 256 MBSubmit: 1943   ...

  2. 【NOIP2017】 Jump house Answer key ( Monotone queue optimization linear DP)

    Preface : The pigeon was killed 1 Six months of blogs ----------------- Topic link The main idea of the topic : The sensitivity of the robot is $d$. It costs... Every time $g$ A gold coin to transform the robot , So the range for the robot to jump right is $[min(d-g,1),m ...

  3. Monotone queue and monotone queue optimization DP

    Monotonic queue definition : In fact, monotonic queue is a kind of queue with monotonic elements , Because of its monotonicity, it is often used to maintain the maximum value of the interval or to reduce DP In order to reduce space and time, the dimension of space has been reduced . General application of monotone queue : 1. Maintain the maximum value of the interval 2 ...

  4. 1855: [Scoi2010] Stock Exchange [ Monotonic queue optimization DP]

    1855: [Scoi2010] Stock Exchange Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 1083  Solved: 519[Submit][Status] ...

  5. $Poj1821\ Fence\ $ Monotonic queue optimization $DP$

    Poj   Acwing Description Yes N A board waiting to be M A craftsman painted , Each board is painted at most once . The first i A craftsman either doesn't paint , Or painting contains blocks of wood Si Of , Length not exceeding Li A continuous piece of wood , Each piece of paint gets P ...

  6. BestCoder Round #89 02 Monotonic queue optimization dp

    1.BestCoder Round #89 2. summary :4 Questions , Can only do A.B, It all depends on hack Top score .. 01  HDU 5944    water 1. The question : A string , Find out how many groups of characters there are y,r,x The subscripts of can form an equal ratio sequence ...

  7. Monotonic queue optimization DP, Multiple backpack

    Monotonic queue optimization DP:http://www.cnblogs.com/ka200812/archive/2012/07/11/2585950.html Monotone queue optimization multiple knapsack :http://blog.csdn ...

  8. bzoj1855: [Scoi2010] Stock Exchange -- Monotonic queue optimization DP

    Monotonic queue optimization DP The template question of It's not hard to list DP equation : In the case of buying because dp[i][j]=max{dp[i-w-1][k]+k*Ap[i]-j*Ap[i]} AP[i]*j Is constant , Maintain... In the queue dp[i-w ...

  9. [poj3017] Cut the Sequence (DP + Monotonic queue optimization + Balance tree optimization )

    DP + Monotonic queue optimization + Balance tree Good question Description Given an integer sequence { an } of length N, you are to cut the se ...

  10. UESTC 880 a birthday present -- Monotonic queue optimization DP

    Definition dp[i][j] It means the first one i Heaven has j When you buy shares , The most money you get . The transfer equation has : 1. Don't buy or sell that day : dp[i][j]=dp[i-1][j]; 2. I bought it the same day j-k stocks : dp[i][j]=max(dp[ ...

Random recommendation

  1. I'm dead in memory --- JAVA The process and linux The size relationship between memories

    Run JAVA use sleep Go to hold live package org.hjb.test; public class TestOnly { public static void main(String[] ...

  2. php The solution to the conflict of concurrent reading and writing files in

    Here we offer 4 A high concurrency scheme for reading and writing files , Each has its advantages. , We can solve it according to our own situation php Concurrent read and write file conflicts . For Japan IP It is not high or the number of concurrent applications is not very large , You don't have to think about it ! There is no problem at all with the general file operation method . But if ...

  3. DataTable Screening , Two ways to bind data sources after filtering (DataTable Of select And use linq return List aggregate )

    General data processing uses DataTable It's going to be a lot , And a lot of the time we'll be right about what we get DataTable After filtering, bind to Combobox.GridView.Repeat And so on , Now share two DataTab ...

  4. utilize memcached Building high performance Web Applications ( Reprint )

    Problems faced For high concurrency and high access Web For applications , Database access bottleneck has always been a headache . Especially when your program architecture is still built in single database mode , And the number of connections in a data pool The value has reached 500 When , Then your program runs away from the edge of crash ...

  5. About form Little problems uploading files

    Usually form It's usually written like this : <form action=" " method="" id="" name=""&g ...

  6. WPS Remove the initial caps and correct them automatically when typing

    1. Click the menu option in the upper left corner 2. Select “ Options ” Button

  7. struts2 request insider Why is it struts2 use EL Expressions can take values

    I don't know if you have ever thought of such a question : Why is it action Instance variables in , Not used request.setAttribute() Method to add a value to request Within the scope of , But in jsp of use EL The expression takes out ? as everyone knows , ...

  8. Data association analysis association analysis (Aprior Algorithm ,python Code )

    1 Basic concepts Shopping basket business (market basket transaction), The following table , Each row in the table corresponds to a transaction , Contains a unique identity TID, And a collection of purchased goods . This paper introduces a method called correlation analysis (association a ...

  9. first CUDA Program

    Start learning CUDA Write a simple one first #include<iostream>__global__ void add( int a, int b, int *c ) { *c = a + b;}in ...

  10. When to use NO_UNNEST

    select * from test a where object_id in (select department_id from hr.dept_1 dept where department_i ...