当前位置:网站首页>Linear DP initial-2-monotone queue optimization

Linear DP initial-2-monotone queue optimization

2021-03-24 17:19:19 Dfkuaid

#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;
}

版权声明
本文为[Dfkuaid]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/03/20210308213440259l.html